結果
問題 | No.2160 みたりのDominator |
ユーザー | 华恋~韵 |
提出日時 | 2024-04-14 10:48:59 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,316 bytes |
コンパイル時間 | 1,476 ms |
コンパイル使用メモリ | 171,772 KB |
実行使用メモリ | 36,688 KB |
最終ジャッジ日時 | 2024-10-03 07:41:51 |
合計ジャッジ時間 | 5,610 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
15,820 KB |
testcase_01 | AC | 12 ms
22,992 KB |
testcase_02 | AC | 4 ms
15,692 KB |
testcase_03 | AC | 6 ms
21,960 KB |
testcase_04 | AC | 5 ms
19,788 KB |
testcase_05 | AC | 5 ms
21,964 KB |
testcase_06 | AC | 5 ms
21,964 KB |
testcase_07 | AC | 5 ms
17,744 KB |
testcase_08 | AC | 4 ms
15,692 KB |
testcase_09 | AC | 3 ms
15,696 KB |
testcase_10 | AC | 4 ms
15,820 KB |
testcase_11 | AC | 4 ms
15,824 KB |
testcase_12 | AC | 4 ms
15,820 KB |
testcase_13 | AC | 4 ms
15,820 KB |
testcase_14 | AC | 4 ms
15,692 KB |
testcase_15 | AC | 4 ms
15,824 KB |
testcase_16 | AC | 5 ms
15,820 KB |
testcase_17 | AC | 4 ms
15,816 KB |
testcase_18 | AC | 4 ms
15,816 KB |
testcase_19 | AC | 4 ms
15,820 KB |
testcase_20 | AC | 4 ms
15,816 KB |
testcase_21 | AC | 5 ms
15,692 KB |
testcase_22 | AC | 4 ms
15,688 KB |
testcase_23 | AC | 5 ms
19,912 KB |
testcase_24 | AC | 5 ms
21,964 KB |
testcase_25 | WA | - |
testcase_26 | AC | 5 ms
21,964 KB |
testcase_27 | AC | 5 ms
21,964 KB |
testcase_28 | WA | - |
testcase_29 | AC | 5 ms
21,836 KB |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | AC | 4 ms
15,820 KB |
testcase_34 | AC | 8 ms
22,604 KB |
testcase_35 | WA | - |
testcase_36 | AC | 4 ms
15,692 KB |
testcase_37 | AC | 6 ms
21,964 KB |
testcase_38 | WA | - |
testcase_39 | AC | 5 ms
17,740 KB |
testcase_40 | AC | 18 ms
22,760 KB |
testcase_41 | AC | 14 ms
23,496 KB |
testcase_42 | AC | 11 ms
19,692 KB |
testcase_43 | AC | 13 ms
20,260 KB |
testcase_44 | AC | 16 ms
25,292 KB |
testcase_45 | AC | 14 ms
20,836 KB |
testcase_46 | AC | 15 ms
25,552 KB |
testcase_47 | AC | 10 ms
19,760 KB |
testcase_48 | AC | 11 ms
22,112 KB |
testcase_49 | AC | 14 ms
25,424 KB |
testcase_50 | AC | 13 ms
20,828 KB |
testcase_51 | AC | 12 ms
20,296 KB |
testcase_52 | AC | 14 ms
24,856 KB |
testcase_53 | AC | 16 ms
20,680 KB |
testcase_54 | AC | 11 ms
17,744 KB |
testcase_55 | AC | 32 ms
26,444 KB |
testcase_56 | WA | - |
testcase_57 | AC | 36 ms
24,688 KB |
testcase_58 | WA | - |
testcase_59 | AC | 32 ms
22,480 KB |
testcase_60 | AC | 29 ms
29,076 KB |
testcase_61 | AC | 29 ms
24,172 KB |
testcase_62 | AC | 35 ms
30,792 KB |
testcase_63 | AC | 32 ms
22,604 KB |
testcase_64 | AC | 29 ms
22,732 KB |
testcase_65 | WA | - |
testcase_66 | WA | - |
testcase_67 | WA | - |
testcase_68 | WA | - |
testcase_69 | WA | - |
testcase_70 | WA | - |
testcase_71 | AC | 15 ms
26,160 KB |
testcase_72 | AC | 24 ms
30,176 KB |
testcase_73 | WA | - |
testcase_74 | WA | - |
testcase_75 | AC | 7 ms
26,200 KB |
testcase_76 | AC | 8 ms
30,444 KB |
testcase_77 | WA | - |
testcase_78 | WA | - |
testcase_79 | AC | 6 ms
22,220 KB |
testcase_80 | AC | 7 ms
30,408 KB |
testcase_81 | AC | 7 ms
22,600 KB |
testcase_82 | AC | 9 ms
26,572 KB |
testcase_83 | AC | 12 ms
20,808 KB |
61_evil_bias_nocross_01.txt | AC | 14 ms
22,868 KB |
61_evil_bias_nocross_02.txt | AC | 14 ms
23,496 KB |
61_evil_bias_nocross_03.txt | AC | 8 ms
17,864 KB |
61_evil_bias_nocross_04.txt | AC | 11 ms
21,900 KB |
61_evil_bias_nocross_05.txt | AC | 13 ms
22,864 KB |
61_evil_bias_nocross_06.txt | AC | 14 ms
20,804 KB |
61_evil_bias_nocross_07.txt | AC | 10 ms
18,128 KB |
61_evil_bias_nocross_08.txt | AC | 14 ms
19,016 KB |
61_evil_bias_nocross_09.txt | AC | 11 ms
20,744 KB |
61_evil_bias_nocross_10.txt | AC | 10 ms
19,404 KB |
61_evil_bias_nocross_11.txt | AC | 9 ms
17,996 KB |
61_evil_bias_nocross_12.txt | AC | 12 ms
18,120 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; }