結果
問題 | No.2667 Constrained Permutation |
ユーザー | chineristAC |
提出日時 | 2024-03-08 22:47:50 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,482 bytes |
コンパイル時間 | 638 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 200,328 KB |
最終ジャッジ日時 | 2024-03-08 22:48:22 |
合計ジャッジ時間 | 29,448 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
56,252 KB |
testcase_01 | AC | 44 ms
56,252 KB |
testcase_02 | AC | 71 ms
72,980 KB |
testcase_03 | AC | 94 ms
76,812 KB |
testcase_04 | AC | 111 ms
78,688 KB |
testcase_05 | AC | 68 ms
72,856 KB |
testcase_06 | AC | 111 ms
78,808 KB |
testcase_07 | AC | 58 ms
68,576 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 70 ms
73,488 KB |
testcase_11 | WA | - |
testcase_12 | AC | 513 ms
112,744 KB |
testcase_13 | AC | 139 ms
78,900 KB |
testcase_14 | AC | 1,319 ms
187,924 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 1,431 ms
190,196 KB |
testcase_19 | AC | 1,141 ms
139,772 KB |
testcase_20 | AC | 1,356 ms
156,220 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 606 ms
124,840 KB |
testcase_25 | AC | 1,146 ms
160,160 KB |
testcase_26 | AC | 1,440 ms
199,332 KB |
testcase_27 | AC | 1,463 ms
200,328 KB |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | AC | 690 ms
122,732 KB |
testcase_39 | AC | 132 ms
78,788 KB |
testcase_40 | AC | 527 ms
110,160 KB |
testcase_41 | AC | 779 ms
123,992 KB |
testcase_42 | AC | 631 ms
116,496 KB |
testcase_43 | AC | 868 ms
120,344 KB |
testcase_44 | AC | 419 ms
97,376 KB |
testcase_45 | AC | 139 ms
78,916 KB |
ソースコード
import sys from itertools import permutations from heapq import heappop,heappush from collections import deque import random import bisect input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) class SegmentTree: def __init__(self, init_val, segfunc, ide_ele): n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num self.size = n for i in range(n): self.tree[self.num + i] = init_val[i] for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, k, x): k += self.num self.tree[k] = x while k > 1: k >>= 1 self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1]) def query(self, l, r): if r==self.size: r = self.num res = self.ide_ele l += self.num r += self.num right = [] while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: right.append(self.tree[r-1]) l >>= 1 r >>= 1 for e in right[::-1]: res = self.segfunc(res,e) return res """ 結婚定理で考える 区間の和集合が区間になるような組のみ考えればいい (区間の長さ)< (区間の数) である組があれば答えは0 そうでないなら条件を満たすkの範囲は区間になっているので、端点を考えればいい """ N = int(input()) lr = [] val_set = set() for i in range(N): l,r = mi() val_set.add(l) val_set.add(r+1) lr.append((l,r+1)) val_set = sorted(val_set) comp = {e:i for i,e in enumerate(val_set)} lr = [(comp[l],comp[r]) for l,r in lr] lr.sort(key=lambda x:x[0],reverse=True) n = len(comp) seg = SegmentTree([0]*n,max,0) L,R = -10**9,10**9 for l,r in lr: t = seg.query(l,r) + 1 ll = val_set[l] L = max(L,t-N+ll-1) seg.update(l,t) seg = SegmentTree([0]*n,max,0) lr.sort(key=lambda x:x[1],reverse=False) for l,r in lr: t = seg.query(l,r) + 1 rr = val_set[r] - 1 R = min(R,rr-t) seg.update(r-1,t) m = min(val_set) for i,(l,r) in enumerate(lr): if val_set[r]-m < i+1: print(0) break else: #assert False print(R-L+1)