結果
問題 |
No.3085 Easy Problems
|
ユーザー |
![]() |
提出日時 | 2025-04-04 22:24:04 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,785 bytes |
コンパイル時間 | 560 ms |
コンパイル使用メモリ | 82,788 KB |
実行使用メモリ | 270,744 KB |
最終ジャッジ日時 | 2025-04-08 13:02:06 |
合計ジャッジ時間 | 55,283 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 TLE * 1 |
ソースコード
import copy import heapq import itertools import math import operator import sys from bisect import bisect, bisect_left, bisect_right, insort from collections import Counter, deque from fractions import Fraction from functools import cmp_to_key, lru_cache, partial from inspect import currentframe from math import ceil, gcd, log10, pi, sqrt # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') input = sys.stdin.readline sys.setrecursionlimit(10000000) # mod = 10 ** 9 + 7 mod = 998244353 # mod = 1 << 128 # mod = 10 ** 30 + 1 INF = 1 << 61 DIFF = 10 ** -9 DX = [1, 0, -1, 0, 1, 1, -1, -1] DY = [0, 1, 0, -1, 1, -1, 1, -1] def read_values(): return tuple(map(int, input().split())) def read_index(): return tuple(map(lambda x: int(x) - 1, input().split())) def read_list(): return list(read_values()) def read_lists(N): return [read_list() for _ in range(N)] def dprint(*values): print(*values, file=sys.stderr) def dprint2(*values): names = {id(v): k for k, v in currentframe().f_back.f_locals.items()} dprint(", ".join(f"{names.get(id(value), '???')}={repr(value)}" for value in values)) class BIT: def __init__(self, N): self.N = N self.T = [0] * (N + 1) def add(self, i, x): i += 1 while i <= self.N: self.T[i] += x i += i & -i def _sum(self, i): s = 0 i += 1 while i > 0: s += self.T[i] i -= i & -i return s #[i, j] def sum(self, i, j): si = self._sum(i - 1) sj = self._sum(j) return sj - si def lower_left(self, v): if v < 0: return -1 x = 0 k = 1 << (self.N.bit_length() - 1) while k > 0: if x + k < self.N and self.T[x + k] < v: v -= self.T[x + k] x += k k //= 2 return x def main(): N = int(input()) L = read_lists(N) Q = int(input()) QL = read_lists(Q) A = sorted(list(set([a for a, _ in QL] + [a for a, _ in L]))) B = [b for _, b in QL] + [b for _, b in L] maxB = max(B) D = {a: i for i, a in enumerate(A)} L = [(D[a], b) for a, b in L] QL = sorted([(b, D[a], i) for i, (a, b) in enumerate(QL)]) BL = [[] for _ in range(maxB + 1)] bit = BIT(len(A) + 1) for a, b in L: BL[b].append((-1, a)) bit.add(a, 1) for b, a, i in QL: BL[b].append((i, a)) res = [0] * Q for S in BL: for i, a in S: if i == -1: bit.add(a, -1) for i, a in S: if i != -1: res[i] = bit.sum(0, a) for i, a in S: if i == -1: bit.add(a, 1) print(*res, sep="\n") if __name__ == "__main__": main()