結果
問題 |
No.1024 Children in a Row
|
ユーザー |
![]() |
提出日時 | 2020-04-11 15:02:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 622 ms / 2,000 ms |
コード長 | 1,908 bytes |
コンパイル時間 | 998 ms |
コンパイル使用メモリ | 116,380 KB |
実行使用メモリ | 36,608 KB |
最終ジャッジ日時 | 2024-09-19 02:28:35 |
合計ジャッジ時間 | 16,933 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; int main() { int n, m; cin>>n>>m; list<int> lst; vector<list<int>::iterator> v(n+m); for(int i=0; i<n; i++){ v[i]=lst.insert(lst.end(), i); } int a[200020], b[200020], k[200020]; int c[200020], d[400040], pr[200020]; bool last[400040]={}; iota(c, c+n, 0); iota(d, d+n, 0); fill(last, last+n, 1); for(int i=0; i<m; i++){ cin>>a[i]>>b[i]>>k[i]; a[i]--; b[i]--; v[n+i]=lst.insert(next(v[c[b[i]]]), n+i); lst.insert(next(v[n+i]), -i-1); last[c[a[i]]]=0; pr[i]=c[a[i]]; c[a[i]]=n+i; d[n+i]=a[i]; last[c[a[i]]]=1; } int idx=0; int l[400040], r[400040], rev[400040]; int s[400040]; s[0]=0; for(auto x:lst){ if(x<0) r[-x-1]=idx; else{ l[x]=idx++; rev[l[x]]=x; s[idx]=s[idx-1]+last[x]; } } for(int i=0; i<m; i++){ int l1=l[n+i], r1=r[i], l2=l[pr[i]], ans; if(l2<l1){ if(k[i]<=s[l2] || k[i]>s[r1]) ans=d[rev[lower_bound(s, s+n+m+1, k[i])-s-1]]; else if(k[i]<=s[l2]+s[r1]-s[l1]) ans=d[rev[lower_bound(s, s+n+m+1, k[i]+s[l1]-s[l2])-s-1]]; else ans=d[rev[lower_bound(s, s+n+m+1, k[i]-s[r1]+s[l1])-s-1]]; }else{ if(k[i]<=s[l1] || k[i]>s[l2]) ans=d[rev[lower_bound(s, s+n+m+1, k[i])-s-1]]; else if(k[i]<=s[l1]+s[l2]-s[r1]) ans=d[rev[lower_bound(s, s+n+m+1, k[i]+s[r1]-s[l1])-s-1]]; else ans=d[rev[lower_bound(s, s+n+m+1, k[i]-s[l2]+s[r1])-s-1]]; } cout<<ans+1<<endl; } return 0; }