結果
問題 | No.1558 Derby Live |
ユーザー | tpc011854 |
提出日時 | 2021-06-26 00:18:51 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 1,993 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 35,360 KB |
実行使用メモリ | 24,176 KB |
最終ジャッジ日時 | 2023-09-07 15:11:42 |
合計ジャッジ時間 | 5,532 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 65 ms
24,000 KB |
testcase_01 | AC | 117 ms
24,096 KB |
testcase_02 | AC | 8 ms
24,100 KB |
testcase_03 | AC | 73 ms
24,068 KB |
testcase_04 | AC | 34 ms
24,092 KB |
testcase_05 | AC | 35 ms
24,056 KB |
testcase_06 | AC | 60 ms
24,068 KB |
testcase_07 | AC | 9 ms
24,028 KB |
testcase_08 | AC | 57 ms
24,084 KB |
testcase_09 | AC | 60 ms
24,176 KB |
testcase_10 | AC | 63 ms
24,116 KB |
testcase_11 | AC | 66 ms
24,136 KB |
testcase_12 | AC | 69 ms
24,164 KB |
testcase_13 | AC | 74 ms
24,000 KB |
testcase_14 | AC | 78 ms
24,000 KB |
testcase_15 | AC | 82 ms
24,132 KB |
testcase_16 | AC | 86 ms
24,100 KB |
testcase_17 | AC | 91 ms
24,100 KB |
testcase_18 | AC | 93 ms
24,096 KB |
testcase_19 | AC | 96 ms
24,092 KB |
testcase_20 | AC | 101 ms
24,036 KB |
testcase_21 | AC | 92 ms
24,080 KB |
testcase_22 | AC | 98 ms
24,060 KB |
testcase_23 | AC | 101 ms
24,064 KB |
testcase_24 | AC | 92 ms
24,056 KB |
testcase_25 | AC | 96 ms
24,068 KB |
testcase_26 | AC | 100 ms
24,040 KB |
testcase_27 | AC | 91 ms
24,104 KB |
testcase_28 | AC | 96 ms
24,108 KB |
testcase_29 | AC | 101 ms
24,100 KB |
testcase_30 | AC | 93 ms
24,068 KB |
testcase_31 | AC | 97 ms
24,096 KB |
testcase_32 | AC | 100 ms
24,072 KB |
testcase_33 | AC | 8 ms
24,100 KB |
testcase_34 | AC | 8 ms
24,084 KB |
ソースコード
#include <cstdio> struct SegT { int l,r; int d[25]; SegT(){ for(int i = 1; i <= 20; i++) d[i] = i; } }; SegT t[200005]; int len = -1; void build(int p,int l,int r){ t[p].l = l, t[p].r = r; if(l==r){ return ; } else{ int m = (l+r)/2; build(2*p, l, m); build(2*p+1, m+1, r); } } SegT merge(const SegT& u, const SegT& v){ SegT res; res.l = u.l, res.r = v.r; for(int i = 1; i <= len; i++) res.d[i] = u.d[v.d[i]]; return res; } void change(int p, int x, int d[]){ if(t[p].l == t[p].r){ for(int i = 1; i <= len; i++) t[p].d[i] = d[i]; } else{ int m = (t[p].l+t[p].r)/2; if(x<=m) change(2*p, x, d); else change(2*p+1,x,d); t[p] = merge(t[2*p],t[2*p+1]); } } SegT ask(int p,int l,int r){ if(l<=t[p].l && r>=t[p].r) return t[p]; else{ int m = (t[p].l+t[p].r)/2; if(r<=m) return ask(2*p, l, r); else if(l>=m+1) return ask(2*p+1, l, r); else return merge(ask(2*p,l,r), ask(2*p+1,l,r)); } } void inv(int d[]){ int dd[25]; for(int i = 1; i <= len; i++){ dd[d[i]] = i; } for(int i = 1; i <= len; i++) d[i] = dd[i]; } int main(){ int n,m,q; scanf("%d%d%d",&n,&m,&q); len = n; build(1,1,m); //printf("done\n"); for(int rnd = 0; rnd < q; rnd++){ int order; scanf("%d",&order); if(order==1){ int p[25]; int u; scanf("%d",&u); for(int i = 1; i <= n; i++) scanf("%d",&p[i]); inv(p); change(1,u,p); } else if(order==2){ int u; scanf("%d",&u); SegT res = ask(1,1,u); for(int i = 1; i <= n; i++) printf("%d ",res.d[i]); printf("\n"); } else{ int u,v; scanf("%d%d",&u,&v); u--; SegT resU; if(u!=0) resU = ask(1,1,u); else for(int i = 1; i <= len; i++) resU.d[i] = i; SegT resV = ask(1,1,v); int rankU[25], rankV[25]; for(int i = 1; i <= n; i++) rankU[resU.d[i]] = i, rankV[resV.d[i]] = i; int res = 0; for(int i = 1; i <= n; i++){ int add = rankV[resU.d[i]] - i; if(add < 0) add *= -1; res += add; } printf("%d\n",res); } } return 0; }