結果
問題 | No.2160 みたりのDominator |
ユーザー | 华恋~韵 |
提出日時 | 2024-04-14 10:48:59 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,316 bytes |
コンパイル時間 | 3,833 ms |
コンパイル使用メモリ | 167,580 KB |
実行使用メモリ | 32,968 KB |
最終ジャッジ日時 | 2024-04-14 10:49:10 |
合計ジャッジ時間 | 7,019 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
15,944 KB |
testcase_01 | AC | 11 ms
25,036 KB |
testcase_02 | AC | 4 ms
15,948 KB |
testcase_03 | AC | 5 ms
21,964 KB |
testcase_04 | AC | 5 ms
19,912 KB |
testcase_05 | AC | 6 ms
22,088 KB |
testcase_06 | AC | 5 ms
21,964 KB |
testcase_07 | AC | 5 ms
17,872 KB |
testcase_08 | AC | 7 ms
15,944 KB |
testcase_09 | AC | 4 ms
15,952 KB |
testcase_10 | AC | 4 ms
15,948 KB |
testcase_11 | AC | 5 ms
15,816 KB |
testcase_12 | AC | 4 ms
15,952 KB |
testcase_13 | AC | 4 ms
15,820 KB |
testcase_14 | AC | 4 ms
15,816 KB |
testcase_15 | AC | 4 ms
15,948 KB |
testcase_16 | AC | 4 ms
15,948 KB |
testcase_17 | AC | 4 ms
15,824 KB |
testcase_18 | AC | 4 ms
15,948 KB |
testcase_19 | AC | 5 ms
15,824 KB |
testcase_20 | AC | 4 ms
15,944 KB |
testcase_21 | AC | 4 ms
15,824 KB |
testcase_22 | AC | 4 ms
15,820 KB |
testcase_23 | AC | 5 ms
20,040 KB |
testcase_24 | AC | 5 ms
22,096 KB |
testcase_25 | WA | - |
testcase_26 | AC | 5 ms
21,960 KB |
testcase_27 | AC | 5 ms
22,096 KB |
testcase_28 | WA | - |
testcase_29 | AC | 6 ms
22,092 KB |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | AC | 4 ms
15,944 KB |
testcase_34 | AC | 10 ms
23,544 KB |
testcase_35 | WA | - |
testcase_36 | AC | 4 ms
15,692 KB |
testcase_37 | AC | 5 ms
22,088 KB |
testcase_38 | WA | - |
testcase_39 | AC | 5 ms
17,868 KB |
testcase_40 | AC | 16 ms
20,908 KB |
testcase_41 | AC | 15 ms
23,200 KB |
testcase_42 | AC | 11 ms
17,992 KB |
testcase_43 | AC | 14 ms
24,780 KB |
testcase_44 | AC | 17 ms
27,208 KB |
testcase_45 | AC | 18 ms
25,672 KB |
testcase_46 | AC | 15 ms
21,708 KB |
testcase_47 | AC | 11 ms
21,964 KB |
testcase_48 | AC | 14 ms
20,208 KB |
testcase_49 | AC | 15 ms
25,100 KB |
testcase_50 | AC | 16 ms
25,676 KB |
testcase_51 | AC | 12 ms
18,248 KB |
testcase_52 | AC | 15 ms
23,248 KB |
testcase_53 | AC | 26 ms
25,080 KB |
testcase_54 | AC | 10 ms
19,792 KB |
testcase_55 | AC | 67 ms
22,604 KB |
testcase_56 | WA | - |
testcase_57 | AC | 88 ms
22,992 KB |
testcase_58 | WA | - |
testcase_59 | AC | 48 ms
24,656 KB |
testcase_60 | AC | 32 ms
30,676 KB |
testcase_61 | AC | 37 ms
24,068 KB |
testcase_62 | AC | 51 ms
26,956 KB |
testcase_63 | AC | 46 ms
22,992 KB |
testcase_64 | AC | 30 ms
28,772 KB |
testcase_65 | WA | - |
testcase_66 | WA | - |
testcase_67 | WA | - |
testcase_68 | WA | - |
testcase_69 | WA | - |
testcase_70 | WA | - |
testcase_71 | AC | 20 ms
22,600 KB |
testcase_72 | AC | 26 ms
30,304 KB |
testcase_73 | WA | - |
testcase_74 | WA | - |
testcase_75 | AC | 8 ms
22,732 KB |
testcase_76 | AC | 7 ms
22,480 KB |
testcase_77 | WA | - |
testcase_78 | WA | - |
testcase_79 | AC | 7 ms
22,220 KB |
testcase_80 | AC | 8 ms
22,604 KB |
testcase_81 | AC | 8 ms
24,076 KB |
testcase_82 | AC | 10 ms
26,700 KB |
testcase_83 | AC | 15 ms
19,016 KB |
61_evil_bias_nocross_01.txt | AC | 16 ms
23,208 KB |
61_evil_bias_nocross_02.txt | AC | 16 ms
25,676 KB |
61_evil_bias_nocross_03.txt | AC | 10 ms
22,216 KB |
61_evil_bias_nocross_04.txt | AC | 12 ms
18,128 KB |
61_evil_bias_nocross_05.txt | AC | 15 ms
22,516 KB |
61_evil_bias_nocross_06.txt | AC | 14 ms
20,252 KB |
61_evil_bias_nocross_07.txt | AC | 11 ms
24,140 KB |
61_evil_bias_nocross_08.txt | AC | 14 ms
21,068 KB |
61_evil_bias_nocross_09.txt | AC | 14 ms
25,552 KB |
61_evil_bias_nocross_10.txt | AC | 12 ms
17,480 KB |
61_evil_bias_nocross_11.txt | AC | 12 ms
22,204 KB |
61_evil_bias_nocross_12.txt | AC | 14 ms
20,512 KB |
ソースコード
#include <bits/stdc++.h> #define ll long long #define pir pair<ll,ll> #define mkp make_pair #define fi first #define se second #define pb push_back using namespace std; const ll maxn=8e6+10; ll n1,n2,n3,m,u,v; void rd(ll &x){ char c; while(!isdigit(c=getchar())) ; x=c-'0'; while(isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0'; } ll l12[maxn],r12[maxn],l13[maxn],r13[maxn],l23[maxn],r23[maxn]; ll c1[maxn],c2[maxn],c3[maxn],s[maxn],cntl,cntr,c[maxn],l,r,sum; __int128 ans; void add(ll i,ll v){ ll tl=max(l23[i],l), tr=min(r23[i],r); if(tl<=tr) sum+=v*(s[tr]-s[tl-1]); c[l23[i]]+=v, c[r23[i]+1]-=v; if(l23[i]<=l&&l<=r23[i]) cntl+=v; if(l23[i]<=r&&r<=r23[i]) cntr+=v; } void print(const __int128 x){ if(x>9) print(x/10); putchar(x%10+'0'); } int main(){ rd(n1), rd(n2), rd(n3), rd(m); for(ll i=1;i<=n1+1;i++) r12[i]=n2+1, r13[i]=n3+1, l12[i]=l13[i]=1; for(ll i=1;i<=n2+1;i++) r23[i]=n3+1, l23[i]=1; for(ll i=1;i<=m;i++){ rd(u), rd(v); if(u>v) swap(u,v); if(u<=n1){ if(v<=n1) ++c1[u+1], --c1[v+1]; else if(v<=n1+n2) v-=n1, r12[u]=min(r12[u],v), l12[u+1]=max(l12[u+1],v+1); else v-=n1+n2, r13[u]=min(r13[u],v), l13[u+1]=max(l13[u+1],v+1); } else if(u<=n1+n2){ u-=n1; if(v<=n1+n2) v-=n1, ++c2[u+1], --c2[v+1]; else v-=n1+n2, r23[u]=min(r23[u],v), l23[u+1]=max(l23[u+1],v+1); } else u-=n1+n2, v-=n1+n2, ++c3[u+1], --c3[v+1]; } for(ll i=1;i<=n1+1;i++) c1[i]+=c1[i-1], l12[i]=max(l12[i],l12[i-1]), l13[i]=max(l13[i],l13[i-1]); for(ll i=1;i<=n2+1;i++) c2[i]+=c2[i-1], l23[i]=max(l23[i],l23[i-1]); for(ll i=1;i<=n3+1;i++) c3[i]+=c3[i-1]; r12[n1+2]=n2+1, r13[n1+2]=r23[n2+2]=n3+1; for(ll i=n1+1;i;i--) c1[i]=!c1[i], r12[i]=min(r12[i],r12[i+1]), r13[i]=min(r13[i],r13[i+1]), l12[i]=min(l12[i],r12[i]+1), l13[i]=min(l13[i],r13[i]+1); for(ll i=n2+1;i;i--) c2[i]=!c2[i], r23[i]=min(r23[i],r23[i+1]), l23[i]=min(l23[i],r23[i]+1); for(ll i=1;i<=n3+1;i++) c3[i]=!c3[i], s[i]=s[i-1]+c3[i]; l12[0]=l13[0]=1; l=1; for(ll i=1;i<=n1+1;i++){ for(ll j=r12[i-1]+1;j<=r12[i];j++) if(c2[j]) add(j,1); for(ll j=l12[i-1];j<l12[i];j++) if(c2[j]) add(j,-1); for(ll j=r13[i-1]+1;j<=r13[i];j++){ cntr+=c[j]; if(c3[j]) sum+=cntr; } for(ll j=l13[i-1];j<l13[i];j++){ if(c3[j]) sum-=cntl; cntl+=c[j+1]; } l=l13[i], r=r13[i]; if(c1[i]) ans+=sum; } print(ans); return 0; }