結果
問題 | No.1386 Range add Simulation |
ユーザー | 👑 Nachia |
提出日時 | 2021-02-07 21:52:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,246 bytes |
コンパイル時間 | 2,269 ms |
コンパイル使用メモリ | 207,048 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-04 15:16:13 |
合計ジャッジ時間 | 19,790 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | RE | - |
testcase_33 | RE | - |
testcase_34 | RE | - |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | WA | - |
testcase_37 | AC | 7 ms
5,376 KB |
testcase_38 | AC | 7 ms
5,376 KB |
testcase_39 | AC | 6 ms
5,376 KB |
testcase_40 | RE | - |
testcase_41 | RE | - |
testcase_42 | RE | - |
testcase_43 | RE | - |
testcase_44 | RE | - |
testcase_45 | RE | - |
testcase_46 | RE | - |
testcase_47 | RE | - |
testcase_48 | RE | - |
testcase_49 | RE | - |
ソースコード
#include <bits/stdc++.h>using namespace std;using LL=long long;using ULL=unsigned long long;#define rep(i,n) for(int i=0; i<(n); i++)struct QueryA{ int c,s; };struct Query{ int c,i,j; };int N,Q;LL B[100000];int ddA[100001];vector<QueryA> A;vector<Query> ans;LL topA=0, topdA=0, topddA=0;LL Alast[3];void query_1(int i){ ans.push_back({1,i+1,0}); B[i]++; }void query_2(int i){ ans.push_back({2,i+1,0}); B[i]--; }void query_3(int i,int j){ ans.push_back({3,i+1,j+1}); B[i]+=B[j]; }void query_4(int i,int j){ ans.push_back({4,i+1,j+1}); B[i]-=B[j]; }void make_k(int i,LL k){if(k>0){ make_k(i,k/2); query_3(i,i); if(k&1) query_1(i); }if(k<0){ make_k(i,-((-k)/2)); query_3(i,i); if(k&1) query_2(i); }}LL add_si(LL s,LL i){ s=abs(s-i)+1; return s*s; }LL simuA[100];void query_A1(int s){ for(int i=s; i<N; i++) simuA[i]+=add_si(s,i); }void query_A2(int s){ for(int i=0; i<=s; i++) simuA[i]+=add_si(s,i); }int main(){scanf("%d%d",&N,&Q);A.resize(Q); rep(i,Q){ int c,s; scanf("%d%d",&c,&s); s--; A[i]={c,s}; }if(N<4){rep(i,N) simuA[i]=0;for(auto q:A){ if(q.c==1) query_A1(q.s); else if(q.c==2) query_A2(q.s); }rep(i,N) B[i]=0;rep(i,N) make_k(i,simuA[i]);}else{rep(i,N+1) ddA[i]=0;rep(i,N){if(A[i].c==1){ddA[A[i].s]++;rep(j,3) if(A[i].s<=N-j-1) Alast[j]+=add_si(N-j-1,A[i].s);}if(A[i].c==2){if(A[i].s<N-2) ddA[A[i].s+2]--;topA+=add_si(0,A[i].s);topdA-=(A[i].s+1)*2+1;topddA+=2;rep(j,3) if(A[i].s>=N-j-1) Alast[j]+=add_si(N-j-1,A[i].s);}}topddA+=ddA[0]*2;topdA+=ddA[0];topA+=ddA[0];rep(i,N) B[i]=0;make_k(0,topA);make_k(N-1,topdA);make_k(N-2,topddA);make_k(N-3,2);for(int i=1; i<N-3; i++){query_3(i,i-1);query_3(N-1,N-2);if(ddA[i]>0) rep(j,ddA[i]){ query_1(N-1); query_3(N-2,N-3); }if(ddA[i]<0) rep(j,-ddA[i]){ query_4(N-2,N-3); query_2(N-1); }query_3(i,N-1);}rep(j,3){ query_4(N-j-1,N-j-1); make_k(N-j-1,Alast[j]); }}printf("%d\n",(int)ans.size());for(auto q:ans){if(q.c<=2) printf("%d %d\n",q.c,q.i);if(q.c>=3) printf("%d %d %d\n",q.c,q.i,q.j);}return 0;}