fork download

import sys
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
 
get_int = [int(x) for x in sys.stdin.buffer.read().split()]
 
n, k = get_int[0], get_int[1]
rows: list[list[int]] = [get_int[2 + i * n: 2 + (i + 1) * n] for i in range(k)]
 
 
class FenwickTree:
    def __init__(self, x):
        bit = self.bit = list(x)
        size = self.size = len(bit)
        for i in range(size):
            j = i | (i + 1)
            if j < size:
                bit[j] += bit[i]
 
    def update(self, idx, x):
        """updates bit[idx] += x"""
        while idx < self.size:
            self.bit[idx] += x
            idx |= idx + 1
 
    def __call__(self, end):
        """calc sum(bit[:end])"""
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x
 
    def find_kth(self, k):
        """Find largest idx such that sum(bit[:idx]) <= k"""
        idx = -1
        for d in reversed(range(self.size.bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < self.size and self.bit[right_idx] <= k:
                idx = right_idx
                k -= self.bit[idx]
        return idx + 1, k
 
class SortedList:
    block_size = 700
 
    def __init__(self, iterable=()):
        self.macro = []
        self.micros = [[]]
        self.micro_size = [0]
        self.fenwick = FenwickTree([0])
        self.size = 0
        for item in iterable:
            self.insert(item)
 
    def insert(self, x):
        i = lower_bound(self.macro, x)
        j = upper_bound(self.micros[i], x)
        self.micros[i].insert(j, x)
        self.size += 1
        self.micro_size[i] += 1
        self.fenwick.update(i, 1)
        if len(self.micros[i]) >= self.block_size:
            self.micros[i:i + 1] = self.micros[i][:self.block_size >> 1], self.micros[i][self.block_size >> 1:]
            self.micro_size[i:i + 1] = self.block_size >> 1, self.block_size >> 1
            self.fenwick = FenwickTree(self.micro_size)
            self.macro.insert(i, self.micros[i + 1][0])
 
    def pop(self, k=-1):
        i, j = self._find_kth(k)
        self.size -= 1
        self.micro_size[i] -= 1
        self.fenwick.update(i, -1)
        return self.micros[i].pop(j)
 
    def __getitem__(self, k):
        i, j = self._find_kth(k)
        return self.micros[i][j]
 
    def count(self, x):
        return self.upper_bound(x) - self.lower_bound(x)
 
    def __contains__(self, x):
        return self.count(x) > 0
 
    def lower_bound(self, x):
        i = lower_bound(self.macro, x)
        return self.fenwick(i) + lower_bound(self.micros[i], x)
 
    def upper_bound(self, x):
        i = upper_bound(self.macro, x)
        return self.fenwick(i) + upper_bound(self.micros[i], x)
 
    def _find_kth(self, k):
        return self.fenwick.find_kth(k + self.size if k < 0 else k)
 
    def __len__(self):
        return self.size
 
    def __iter__(self):
        return (x for micro in self.micros for x in micro)
 
    def __repr__(self):
        return str(list(self))
 
 
worst: int = -1
worst_idx: int = -1
for row in range(k):
    curr: int = 0
    sorted_list: SortedList = SortedList([rows[row][0]])
    for soldier_idx in range(1, n):
        sorted_list.insert(rows[row][soldier_idx])
        soldier_idx_in_sorted_list: int = sorted_list.lower_bound(rows[row][soldier_idx])
        curr += len(sorted_list) - 1 - soldier_idx_in_sorted_list
    if curr > worst:
        worst = curr
        worst_idx = row
 
print(worst_idx + 1)
 

Main.java:1: error: '.' expected
import sys
          ^
Main.java:2: error: ';' expected
from bisect import bisect_left as lower_bound
    ^
Main.java:2: error: '.' expected
from bisect import bisect_left as lower_bound
                              ^
Main.java:2: error: ';' expected
from bisect import bisect_left as lower_bound
                                 ^
Main.java:3: error: '.' expected
from bisect import bisect_right as upper_bound
                               ^
Main.java:3: error: ';' expected
from bisect import bisect_right as upper_bound
                                  ^
Main.java:11: error: '{' expected
class FenwickTree:
                 ^
Main.java:17: error: > expected
            if j < size:
                       ^
Main.java:18: error: ']' expected
                bit[j] += bit[i]
                    ^
Main.java:18: error: ';' expected
                bit[j] += bit[i]
                     ^
Main.java:18: error: ']' expected
                bit[j] += bit[i]
                              ^
Main.java:18: error: ';' expected
                bit[j] += bit[i]
                               ^
Main.java:20: error: <identifier> expected
    def update(self, idx, x):
                   ^
Main.java:20: error: <identifier> expected
    def update(self, idx, x):
                        ^
Main.java:20: error: <identifier> expected
    def update(self, idx, x):
                           ^
Main.java:20: error: ';' expected
    def update(self, idx, x):
                            ^
Main.java:22: error: > expected
        while idx < self.size:
                        ^
Main.java:22: error: <identifier> expected
        while idx < self.size:
                             ^
Main.java:23: error: ']' expected
            self.bit[idx] += x
                     ^
Main.java:23: error: ';' expected
            self.bit[idx] += x
                        ^
Main.java:24: error: ';' expected
            idx |= idx + 1
               ^
Main.java:24: error: <identifier> expected
            idx |= idx + 1
                      ^
Main.java:26: error: <identifier> expected
    def __call__(self, end):
                     ^
Main.java:26: error: <identifier> expected
    def __call__(self, end):
                          ^
Main.java:26: error: ';' expected
    def __call__(self, end):
                           ^
Main.java:39: error: > expected
            if right_idx < self.size and self.bit[right_idx] <= k:
                               ^
Main.java:39: error: ';' expected
            if right_idx < self.size and self.bit[right_idx] <= k:
                                        ^
Main.java:39: error: ']' expected
            if right_idx < self.size and self.bit[right_idx] <= k:
                                                  ^
Main.java:39: error: ';' expected
            if right_idx < self.size and self.bit[right_idx] <= k:
                                                           ^
Main.java:39: error: <identifier> expected
            if right_idx < self.size and self.bit[right_idx] <= k:
                                                                 ^
Main.java:40: error: <identifier> expected
                idx = right_idx
                   ^
Main.java:40: error: ';' expected
                idx = right_idx
                               ^
Main.java:41: error: <identifier> expected
                k -= self.bit[idx]
                                  ^
Main.java:42: error: <identifier> expected
        return idx + 1, k
                  ^
Main.java:42: error: <identifier> expected
        return idx + 1, k
                         ^
Main.java:44: error: '{' expected
class SortedList:
                ^
Main.java:95: error: <identifier> expected
        return self.fenwick.find_kth(k + self.size if k < 0 else k)
                                                         ^
Main.java:95: error: illegal start of type
        return self.fenwick.find_kth(k + self.size if k < 0 else k)
                                                          ^
Main.java:95: error: <identifier> expected
        return self.fenwick.find_kth(k + self.size if k < 0 else k)
                                                                  ^
Main.java:97: error: <identifier> expected
    def __len__(self):
                    ^
Main.java:97: error: ';' expected
    def __len__(self):
                     ^
Main.java:107: error: <identifier> expected
worst: int = -1
          ^
Main.java:107: error: ';' expected
worst: int = -1
               ^
Main.java:108: error: <identifier> expected
worst_idx: int = -1
         ^
Main.java:108: error: <identifier> expected
worst_idx: int = -1
              ^
Main.java:108: error: ';' expected
worst_idx: int = -1
                   ^
Main.java:109: error: ';' expected
for row in range(k):
          ^
Main.java:109: error: invalid method declaration; return type required
for row in range(k):
           ^
Main.java:109: error: <identifier> expected
for row in range(k):
                  ^
Main.java:109: error: ';' expected
for row in range(k):
                   ^
Main.java:110: error: <identifier> expected
    curr: int = 0
             ^
Main.java:110: error: ';' expected
    curr: int = 0
                 ^
Main.java:111: error: <identifier> expected
    sorted_list: SortedList = SortedList([rows[row][0]])
               ^
Main.java:111: error: <identifier> expected
    sorted_list: SortedList = SortedList([rows[row][0]])
                           ^
Main.java:111: error: illegal start of expression
    sorted_list: SortedList = SortedList([rows[row][0]])
                                         ^
Main.java:111: error: ';' expected
    sorted_list: SortedList = SortedList([rows[row][0]])
                                                       ^
Main.java:112: error: ';' expected
    for soldier_idx in range(1, n):
                      ^
Main.java:112: error: invalid method declaration; return type required
    for soldier_idx in range(1, n):
                       ^
Main.java:112: error: illegal start of type
    for soldier_idx in range(1, n):
                             ^
Main.java:114: error: <identifier> expected
        soldier_idx_in_sorted_list: int = sorted_list.lower_bound(rows[row][soldier_idx])
                                       ^
Main.java:114: error: ';' expected
        soldier_idx_in_sorted_list: int = sorted_list.lower_bound(rows[row][soldier_idx])
                                                                                         ^
Main.java:115: error: <identifier> expected
        curr += len(sorted_list) - 1 - soldier_idx_in_sorted_list
                                                                 ^
Main.java:116: error: <identifier> expected
    if curr > worst:
           ^
Main.java:116: error: <identifier> expected
    if curr > worst:
                   ^
Main.java:117: error: <identifier> expected
        worst = curr
             ^
Main.java:117: error: ';' expected
        worst = curr
                    ^
Main.java:118: error: <identifier> expected
        worst_idx = row
                 ^
Main.java:118: error: ';' expected
        worst_idx = row
                       ^
Main.java:120: error: invalid method declaration; return type required
print(worst_idx + 1)
^
Main.java:120: error: <identifier> expected
print(worst_idx + 1)
               ^
Main.java:120: error: reached end of file while parsing
print(worst_idx + 1)
                    ^
71 errors

Standard output is empty