結果
問題 | No.2667 Constrained Permutation |
ユーザー | chineristAC |
提出日時 | 2024-03-08 23:26:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,713 ms / 2,000 ms |
コード長 | 4,565 bytes |
コンパイル時間 | 166 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 255,380 KB |
最終ジャッジ日時 | 2024-03-08 23:27:32 |
合計ジャッジ時間 | 30,657 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 49 ms
58,340 KB |
testcase_01 | AC | 47 ms
58,340 KB |
testcase_02 | AC | 57 ms
66,496 KB |
testcase_03 | AC | 64 ms
71,000 KB |
testcase_04 | AC | 101 ms
78,000 KB |
testcase_05 | AC | 56 ms
66,492 KB |
testcase_06 | AC | 95 ms
77,868 KB |
testcase_07 | AC | 54 ms
66,496 KB |
testcase_08 | AC | 101 ms
77,860 KB |
testcase_09 | AC | 103 ms
77,868 KB |
testcase_10 | AC | 63 ms
68,548 KB |
testcase_11 | AC | 92 ms
77,900 KB |
testcase_12 | AC | 561 ms
126,312 KB |
testcase_13 | AC | 92 ms
78,268 KB |
testcase_14 | AC | 1,649 ms
233,736 KB |
testcase_15 | AC | 1,006 ms
151,432 KB |
testcase_16 | AC | 661 ms
132,080 KB |
testcase_17 | AC | 284 ms
89,804 KB |
testcase_18 | AC | 1,659 ms
241,520 KB |
testcase_19 | AC | 1,578 ms
183,132 KB |
testcase_20 | AC | 1,713 ms
166,136 KB |
testcase_21 | AC | 1,215 ms
181,624 KB |
testcase_22 | AC | 1,182 ms
170,772 KB |
testcase_23 | AC | 1,283 ms
181,912 KB |
testcase_24 | AC | 699 ms
155,072 KB |
testcase_25 | AC | 1,353 ms
213,544 KB |
testcase_26 | AC | 1,687 ms
255,380 KB |
testcase_27 | AC | 1,667 ms
250,928 KB |
testcase_28 | AC | 727 ms
184,616 KB |
testcase_29 | AC | 905 ms
200,320 KB |
testcase_30 | AC | 799 ms
212,864 KB |
testcase_31 | AC | 577 ms
170,676 KB |
testcase_32 | AC | 156 ms
86,536 KB |
testcase_33 | AC | 574 ms
97,472 KB |
testcase_34 | AC | 306 ms
87,872 KB |
testcase_35 | AC | 362 ms
89,916 KB |
testcase_36 | AC | 348 ms
88,948 KB |
testcase_37 | AC | 383 ms
90,984 KB |
testcase_38 | AC | 932 ms
133,028 KB |
testcase_39 | AC | 111 ms
78,484 KB |
testcase_40 | AC | 231 ms
86,296 KB |
testcase_41 | AC | 387 ms
97,660 KB |
testcase_42 | AC | 821 ms
135,196 KB |
testcase_43 | AC | 1,124 ms
140,424 KB |
testcase_44 | AC | 514 ms
106,732 KB |
testcase_45 | AC | 91 ms
78,104 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 def checK_zero(N,_lr): lr = _lr[:] lr.sort(key=lambda x:x[0],reverse=True) nxt_num = 0 pq = [] while lr or pq: while lr and lr[-1][0] <= nxt_num: l,r = lr.pop() heappush(pq,r) #print(lr,pq,nxt_num) if pq: r = heappop(pq) if r < nxt_num: #print("ban!",pq,lr,nxt_num) return False nxt_num += 1 else: l,r = lr[-1] nxt_num = l return True def check_k(N,k,_lr): lr = [(l-k,r-k) for l,r in _lr] lr.sort(key=lambda x:x[0],reverse=True) pq = [] for i in range(1,N+1): while lr and lr[-1][0] <= i: heappush(pq,lr.pop()[1]) if not pq: return False r = heappop(pq) if r < i: return False return True def solve_brute(N,lr): res = [] R = max(r for l,r in lr) for k in range(-N,R+1): if check_k(N,k,lr): res.append(k) return res def solve(N,_lr): if not checK_zero(N,_lr): return 0 return [] lr = [(l,r+1) for l,r in _lr] """ 結婚定理で考える 区間の和集合が区間になるような組のみ考えればいい (区間の長さ)< (区間の数) である組があれば答えは0 = 相異なる整数を割り当てられるか? そうでないなら条件を満たすkの範囲は区間になっているので、端点を考えればいい """ val_set = set() for i,(l,r) in enumerate(lr): val_set.add(l) val_set.add(r) 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) cnt = [0] * (n) for l,r in lr: cnt[l] += 1 cnt[r] -= 1 for i in range(1,n): cnt[i] += cnt[i-1] if 0 in cnt[:n-1]: return 0 return [] L,R = -10**9,10**9 for i,(l,r) in enumerate(lr): t = i + 1 ll = val_set[l] L = max(L,t-N+ll-1) lr.sort(key=lambda x:(x[1],x[0]),reverse=False) for i,(l,r) in enumerate(lr): t = i + 1 rr = val_set[r] - 1 R = min(R,rr-t) #print("LR",L,R) if L <= R: return R-L+1 return [k for k in range(L,R+1)] else: return 0 return [] def make_test(N): lr = [] for i in range(N): l = random.randint(1,2*N) r = random.randint(l,2*N) lr.append((l,r)) return lr while False: N = random.randint(1,10) lr = make_test(N) #N = 2 #lr = [(1,4),(4,4)] #N = 3 #lr = [(5,6),(6,6),(5,5)] #N = 4 #lr = [(1,5),(5,7),(3,7),(7,7)] #N = 4 #lr = [(2,7),(2,4),(4,6),(3,3)] res = solve(N,lr) exp = solve_brute(N,lr) if res != exp: print("WA") print(N) print(lr) print("res",res) print("exp",exp) break else: print("AC",N) N = int(input()) lr = [tuple(mi()) for i in range(N)] print(solve(N,lr))