結果
問題 | No.2220 Range Insert & Point Mex |
ユーザー | 沙耶花 |
提出日時 | 2023-02-17 21:50:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 444 ms / 2,000 ms |
コード長 | 1,402 bytes |
コンパイル時間 | 4,404 ms |
コンパイル使用メモリ | 270,988 KB |
実行使用メモリ | 41,896 KB |
最終ジャッジ日時 | 2023-09-28 18:01:05 |
合計ジャッジ時間 | 15,468 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 440 ms
41,620 KB |
testcase_14 | AC | 444 ms
41,644 KB |
testcase_15 | AC | 430 ms
41,896 KB |
testcase_16 | AC | 431 ms
41,744 KB |
testcase_17 | AC | 436 ms
41,708 KB |
testcase_18 | AC | 433 ms
41,620 KB |
testcase_19 | AC | 439 ms
41,712 KB |
testcase_20 | AC | 386 ms
35,424 KB |
testcase_21 | AC | 386 ms
35,544 KB |
testcase_22 | AC | 388 ms
35,544 KB |
testcase_23 | AC | 361 ms
25,132 KB |
testcase_24 | AC | 262 ms
22,640 KB |
testcase_25 | AC | 272 ms
20,884 KB |
testcase_26 | AC | 327 ms
22,500 KB |
testcase_27 | AC | 142 ms
11,172 KB |
testcase_28 | AC | 179 ms
14,476 KB |
testcase_29 | AC | 188 ms
14,664 KB |
testcase_30 | AC | 189 ms
14,692 KB |
testcase_31 | AC | 302 ms
22,244 KB |
testcase_32 | AC | 256 ms
20,936 KB |
testcase_33 | AC | 271 ms
21,108 KB |
testcase_34 | AC | 351 ms
28,428 KB |
testcase_35 | AC | 380 ms
28,236 KB |
testcase_36 | AC | 333 ms
23,696 KB |
testcase_37 | AC | 357 ms
23,640 KB |
testcase_38 | AC | 355 ms
35,048 KB |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 int main(){ int n; cin>>n; vector<int> t; vector<int> l(n),r(n),a(n); rep(i,n){ cin>>l[i]>>r[i]>>a[i]; r[i]++; t.push_back(l[i]); t.push_back(r[i]); } int q; cin>>q; vector<int> x(q); rep(i,q){ cin>>x[i]; t.push_back(x[i]); } sort(t.begin(),t.end()); t.erase(unique(t.begin(),t.end()),t.end()); vector<vector<int>> Add(t.size()),Del(t.size()),Que(t.size()); rep(i,n){ l[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),l[i])); r[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),r[i])); if(a[i]>=n+5)continue; Add[l[i]].push_back(i); Del[r[i]].push_back(i); } rep(i,q){ x[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),x[i])); Que[x[i]].push_back(i); } set<int> None; rep(i,n+5)None.insert(i); vector<int> c(n+5,0); vector<int> ans(q); rep(i,t.size()){ rep(j,Add[i].size()){ int xx = a[Add[i][j]]; c[xx]++; if(c[xx]==1)None.erase(xx); } rep(j,Del[i].size()){ int xx = a[Del[i][j]]; c[xx]--; if(c[xx]==0)None.insert(xx); } rep(j,Que[i].size()){ int xx = Que[i][j]; ans[xx] = *(None.begin()); } } rep(i,q){ cout<<ans[i]<<endl; } return 0; }