QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#532050 | #9228. ICPC Inference | ucup-team3586# | AC ✓ | 1422ms | 183104kb | C++23 | 4.6kb | 2024-08-24 23:47:33 | 2024-08-24 23:47:33 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const int Count=13,Penalty=20;
const int Thres=400205;
const int B=450;
int n,d,L;
vector<int> vec[200200];
ll l[200200],r[200200];
vector<int> pool;
inline ll gen(int pc,ll tot){return (pc>2)?0:(pc==2?ub(pool,tot):tot+400400);}
int sp[200200];
int val[Thres+25];
vector<int> gen(int ind)
{
if(sz(vec[ind])>B)
{
memset(val,-1,sizeof(val));
for(int i=0;i<sz(vec[ind]);i++)
val[vec[ind][i]]=i;
for(int i=0;i<Thres+5;i++)
if(val[i]>0)
val[i+Penalty]=max(val[i+Penalty],val[i]-1);
vector<int> ret;
for(int i=0;i<=Thres;i++) if(val[i]!=-1)
ret.pb(i);
for(int i=Thres+1;i<Thres+25;i++) if(val[i]!=-1)
{
ret.pb(i);
break;
}
for(auto &x:ret) x+=400400;
if(sz(vec[ind])>1) ret.insert(ret.begin(),gen(2,vec[ind].back()+vec[ind][sz(vec[ind])-2]+(sz(vec[ind])-2)*Penalty));
return ret;
}
else
{
vector<int> ret;
for(int i=0;i<sz(vec[ind]);i++)
for(int j=0;j<=i;j++)
ret.pb(j*Penalty+vec[ind][i]);
srt(ret);
uni(ret);
while(sz(ret)>1&&ret[sz(ret)-2]>Thres) ret.pop_back();
for(auto &x:ret) x+=400400;
if(sz(vec[ind])>1) ret.insert(ret.begin(),gen(2,vec[ind].back()+vec[ind][sz(vec[ind])-2]+(sz(vec[ind])-2)*Penalty));
return ret;
}
}
int s1[800800],s2[800800];
int cnt[800800][30];
int segt[800800*20];
int ls[800800*20],rs[800800*20],tot;
int update(int x,int l,int r,int p,int v)
{
int ret=++tot;
segt[ret]=segt[x]+v;
ls[ret]=ls[x];
rs[ret]=rs[x];
if(l==r) return ret;
int mid=(l+r)/2;
if(p<=mid)
ls[ret]=update(ls[x],l,mid,p,v);
else
rs[ret]=update(rs[x],mid+1,r,p,v);
return ret;
}
int query(int x,int l,int r,int ql,int qr)
{
if(!x) return 0;
if(l==ql&&r==qr) return segt[x];
int mid=(l+r)/2;
if(qr<=mid)
return query(ls[x],l,mid,ql,qr);
if(ql>mid)
return query(rs[x],mid+1,r,ql,qr);
return query(ls[x],l,mid,ql,mid)+query(rs[x],mid+1,r,mid+1,qr);
}
int rt[800800];
vector<int> vq[800800];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>d>>L;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
vec[x].pb(y);
}
int tot=0;
for(int i=1;i<=d;i++) if(sz(vec[i])==2)
pool.pb(vec[i][0]+vec[i][1]);
for(int i=1;i<=d;i++) if(sz(vec[i])>1)
pool.pb(vec[i].back()+vec[i][sz(vec[i])-2]+(sz(vec[i])-2)*Penalty);
srt(pool);
uni(pool);
for(int i=1;i<=d;i++) if(sz(vec[i]))
{
tot++;
int pc=0;
ll tot=0;
for(auto x:vec[i])
if(pc<Count)
{
pc++;
tot+=x;
}
l[i]=gen(pc,tot);
ll tot2=vec[i].back()+(sz(vec[i])-1)*Penalty;
r[i]=gen(1,tot2);
if(r[i]>Thres+400400)
sp[i]=1;
s1[l[i]]++;
if(!sp[i])
s2[r[i]]++;
if(r[i]-l[i]<30)
cnt[l[i]][r[i]-l[i]]++;
vq[l[i]].pb(min(800800ll,r[i]));
}
for(int i=0;i<800800;i++)
for(int j=1;j<30;j++)
cnt[i][j]+=cnt[i][j-1];
for(int i=1;i<800800;i++)
{
s1[i]+=s1[i-1];
s2[i]+=s2[i-1];
}
for(int i=0;i<800800;i++)
{
if(i) rt[i]=rt[i-1];
for(auto x:vq[i])
rt[i]=update(rt[i],0,800800,x,1);
}
ll ans=0;
vector<int> vsp;
for(int i=1;i<=d;i++)
if(sp[i])
vsp.pb(i);
for(int i=1;i<=d;i++)
{
vector<int> times=gen(i);
if(!sz(times)) continue;
int lst=-1;
int idx=i;
for(int i=0;i<sz(times);i++)
{
int cur=times[i];
int L=s1[cur]-(lst>=0?s1[lst]:0);
int R=s2[800800-1]-(cur>0?s2[cur-1]:0);
if(l[idx]>lst&&l[idx]<=cur) L--;
if(r[idx]>=cur&&!sp[idx]) R--;
lst=cur;
ans+=1ll*L*R;
}
int val=times.back();
int R=0,L=s1[val];
if(l[idx]<=val) L--;
for(auto idx2:vsp)
if(idx2!=i&&r[idx2]>=val)
R++;
ans+=1ll*L*R;
ans-=(tot)-(s1[800800-1]-s1[val])-(times[0]>0?s2[times[0]-1]:0)-1;
for(int i=1;i<sz(times);i++)
if(times[i]-times[i-1]>=30)
ans+=query(rt[times[i]-1],0,800800,times[i-1]+1,times[i]-1)-query(rt[times[i-1]],0,800800,times[i-1]+1,times[i]-1);
else
for(int j=1;j<times[i]-times[i-1];j++)
ans+=cnt[times[i-1]+j][times[i]-times[i-1]-j-1];
}
cout<<ans<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 12ms
memory: 108900kb
input:
4 3 300 1 10 2 25 2 30 3 50
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 23ms
memory: 109312kb
input:
4 6 200000 6 1 6 1 1 2 2 2
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 60ms
memory: 131192kb
input:
191580 64997 56 24878 1 35060 1 24245 1 64330 1 9650 1 15423 1 34953 1 21456 1 36718 1 21395 1 17613 1 16995 1 45257 1 31277 1 20026 1 1870 1 25581 1 9997 1 54701 1 30752 1 32269 1 705 1 64186 1 58881 1 24614 1 55311 1 18259 1 58886 1 23296 1 17628 1 3411 1 37469 1 47951 1 12188 1 60720 1 54168 1 45...
output:
274533940012863
result:
ok 1 number(s): "274533940012863"
Test #4:
score: 0
Accepted
time: 106ms
memory: 141448kb
input:
192309 96431 357 56446 1 42487 1 47313 1 71736 1 74439 1 19895 1 52024 1 66203 1 992 1 78744 1 9911 1 85130 1 73814 1 64499 1 92961 1 66255 1 88807 1 82217 1 36788 1 66999 1 35107 1 47933 1 34196 1 50534 1 83014 1 75035 1 30407 1 36014 1 7248 1 69915 1 57348 1 5356 1 37088 1 36455 1 29365 1 71376 1 ...
output:
868523468626161
result:
ok 1 number(s): "868523468626161"
Test #5:
score: 0
Accepted
time: 434ms
memory: 115796kb
input:
200000 200000 200000 151464 4 1477 6 95966 8 121582 8 19239 11 668 13 109329 15 173254 15 153807 16 75865 16 123829 17 101156 17 8881 18 116717 18 124985 18 125918 18 132143 19 35899 20 90547 20 106065 22 176481 23 11727 23 527 24 77206 25 85757 25 169873 26 139187 26 5970 28 37134 29 199855 30 9598...
output:
149096043
result:
ok 1 number(s): "149096043"
Test #6:
score: 0
Accepted
time: 43ms
memory: 109032kb
input:
200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000...
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 210ms
memory: 155100kb
input:
200000 200000 200000 80855 2 16643 3 158423 4 160007 6 83405 9 148393 10 94889 10 146919 11 56648 12 60318 12 182241 13 144187 14 96195 16 72396 16 10048 17 32575 19 75743 21 49152 21 21380 22 64386 28 11608 29 49440 30 125557 35 170781 36 5487 37 104466 37 136650 37 84688 38 38173 40 122020 40 9383...
output:
689247584152428
result:
ok 1 number(s): "689247584152428"
Test #8:
score: 0
Accepted
time: 158ms
memory: 125584kb
input:
200000 28000 200000 5152 1 5152 1 26010 1 12173 1 12173 1 12166 1 26010 1 24704 1 12173 1 24704 1 26010 1 12071 1 12173 1 12173 1 12166 1 26010 1 24704 1 12166 1 6044 1 24704 1 6044 1 12173 1 24704 1 6733 1 12173 1 12166 1 12173 1 12166 1 24704 1 12166 1 24704 1 12166 1 5152 1 12166 1 12166 1 26010 ...
output:
13273777158527
result:
ok 1 number(s): "13273777158527"
Test #9:
score: 0
Accepted
time: 11ms
memory: 109016kb
input:
4 6 200000 6 1 6 1 1 2 2 2
output:
4
result:
ok 1 number(s): "4"
Test #10:
score: 0
Accepted
time: 120ms
memory: 147300kb
input:
199999 200000 199995 22477 1 124061 1 102846 2 124061 2 124061 3 124061 3 124061 4 124061 5 59212 5 169893 5 124061 6 80004 6 112429 7 31273 11 124061 12 67631 12 124061 14 10017 15 124061 16 70773 16 124061 17 168853 18 88973 19 124061 19 61672 19 196994 20 48373 21 113531 22 92390 23 152850 25 998...
output:
150416508568041
result:
ok 1 number(s): "150416508568041"
Test #11:
score: 0
Accepted
time: 24ms
memory: 107172kb
input:
3 199993 199995 165540 12988 2883 39410 66825 115392
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 82ms
memory: 132408kb
input:
193973 65702 62 51610 1 53512 1 12563 1 56075 1 29395 1 42082 1 60371 1 17038 1 29443 1 33664 1 12471 1 34225 1 49958 1 54960 1 59860 1 33819 1 7499 1 34862 1 6704 1 52200 1 22803 1 7726 1 61422 1 51120 1 17203 1 11462 1 13292 1 20641 1 21050 1 28979 1 35347 1 55821 1 52326 1 50557 1 8296 1 53862 1 ...
output:
283586156841885
result:
ok 1 number(s): "283586156841885"
Test #13:
score: 0
Accepted
time: 118ms
memory: 177872kb
input:
199975 199975 100000 27676 1 116023 2 40052 2 154967 2 82099 3 2503 4 159303 5 136744 5 89330 6 117095 6 182013 6 131786 7 180992 7 73734 7 122549 8 16427 8 104713 8 46057 9 63743 9 160535 10 109106 11 135371 12 65002 13 194754 14 15088 15 144270 15 106306 15 84597 16 143308 16 67042 16 103147 17 15...
output:
1332840068163275
result:
ok 1 number(s): "1332840068163275"
Test #14:
score: 0
Accepted
time: 428ms
memory: 113544kb
input:
200000 312 200000 155 1 241 1 93 1 157 1 308 1 7 1 148 1 240 1 172 1 77 1 151 1 141 1 150 1 190 1 226 1 265 1 247 1 171 1 251 1 115 1 164 1 185 1 234 1 176 1 63 1 21 1 107 1 132 1 224 1 293 1 80 1 162 1 113 1 243 1 287 1 104 1 298 1 197 1 270 1 6 1 252 1 289 1 2 1 160 1 229 1 116 1 165 1 216 1 159 1...
output:
30079920
result:
ok 1 number(s): "30079920"
Test #15:
score: 0
Accepted
time: 15ms
memory: 109116kb
input:
24 16 200000 6 1 5 2 9 3 6 3 6 3 1 4 15 12 11 13 15 13 14 13 11 13 14 14 12 22 8 23 16 24 10 42 2 43 4 44 13 199998 13 199998 13 199998 7 199999 7 199999 3 200000
output:
1479
result:
ok 1 number(s): "1479"
Test #16:
score: 0
Accepted
time: 82ms
memory: 154228kb
input:
199998 140790 200000 20382 1 75175 1 1261 1 30469 1 8689 1 134949 1 10677 1 33222 1 42480 1 80518 1 111286 1 125548 1 78740 1 1530 1 98335 1 76194 1 56788 1 113516 1 101478 1 101211 1 112396 1 62315 1 119913 1 70262 1 16488 1 135245 1 24429 1 17435 1 61254 1 98349 1 11844 1 15041 1 11510 1 71156 1 6...
output:
1101885707898743
result:
ok 1 number(s): "1101885707898743"
Test #17:
score: 0
Accepted
time: 80ms
memory: 125696kb
input:
196811 51280 24 17192 1 25079 1 27464 1 39867 1 1832 1 17482 1 4693 1 4819 1 15064 1 39031 1 24107 1 29585 1 6585 1 33020 1 47567 1 13253 1 39048 1 1418 1 25729 1 45804 1 24904 1 14061 1 4574 1 28867 1 48344 1 9938 1 27903 1 16751 1 23071 1 21052 1 36834 1 45839 1 8894 1 8677 1 34756 1 19157 1 40181...
output:
134808013718613
result:
ok 1 number(s): "134808013718613"
Test #18:
score: 0
Accepted
time: 12ms
memory: 109128kb
input:
13 10 200000 10 1 10 3 10 3 1 20 7 21 5 22 9 62 8 63 3 64 4 199979 4 199979 2 200000 2 200000
output:
184
result:
ok 1 number(s): "184"
Test #19:
score: 0
Accepted
time: 24ms
memory: 109120kb
input:
1000 514 100 276 1 169 1 267 1 386 1 305 1 301 1 190 1 392 1 22 2 93 2 3 2 245 2 327 2 317 2 425 2 292 2 252 2 212 2 377 2 255 3 108 3 352 3 399 3 369 3 45 3 282 3 236 3 371 3 434 3 439 3 71 3 231 3 314 3 7 3 434 3 389 4 87 4 57 4 313 4 219 4 381 4 222 5 492 5 194 5 148 5 186 5 21 5 185 5 170 6 394 ...
output:
102673572
result:
ok 1 number(s): "102673572"
Test #20:
score: 0
Accepted
time: 719ms
memory: 135676kb
input:
200000 114052 200000 95 1 55490 2 61481 2 29754 3 104570 5 97903 6 89479 11 88722 13 54292 13 5540 16 31838 17 48936 19 112373 20 48291 20 90401 22 42152 23 30304 26 8433 28 66247 28 49887 32 80338 33 57507 39 65209 42 37033 45 9055 45 93908 49 11908 50 48143 51 108424 51 107522 55 106177 56 51263 5...
output:
88358595246486
result:
ok 1 number(s): "88358595246486"
Test #21:
score: 0
Accepted
time: 41ms
memory: 106792kb
input:
4 3 300 1 10 2 25 2 30 3 50
output:
3
result:
ok 1 number(s): "3"
Test #22:
score: 0
Accepted
time: 136ms
memory: 183104kb
input:
200000 200000 200000 94701 3 156689 6 61741 6 155743 8 107012 8 169644 9 92832 11 120561 11 121290 12 831 13 152158 16 196171 16 128201 18 132493 19 81786 21 69528 21 18357 22 47647 22 168114 23 52100 23 151112 23 128866 25 119837 26 12669 30 184846 31 168755 32 29744 33 138894 41 191980 41 89643 42...
output:
1333333381066300
result:
ok 1 number(s): "1333333381066300"
Test #23:
score: 0
Accepted
time: 15ms
memory: 109112kb
input:
3 3 3 1 1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 222ms
memory: 150632kb
input:
200000 200000 200000 59008 1 52339 3 56532 4 39193 4 36351 4 196219 4 121276 4 171679 6 59990 7 173361 8 13495 8 34421 9 194365 9 152300 10 122594 10 31107 11 24540 11 14394 11 147019 12 148917 15 124501 16 119218 17 9372 18 37864 18 57690 22 127336 22 15616 22 95247 23 100393 24 177953 27 17061 28 ...
output:
962377606544272
result:
ok 1 number(s): "962377606544272"
Test #25:
score: 0
Accepted
time: 19ms
memory: 109280kb
input:
1024 146 997 54 1 101 1 76 1 104 1 130 1 141 1 8 1 131 1 54 1 54 1 122 1 134 1 45 1 100 1 8 1 44 1 68 2 104 2 130 2 76 2 44 2 141 2 141 2 68 2 131 2 54 2 101 2 122 2 100 2 143 2 8 2 68 2 51 2 44 2 134 2 8 2 8 3 36 3 131 3 76 3 8 3 54 3 122 3 134 3 100 3 128 3 101 3 68 3 8 3 141 3 68 3 68 3 117 3 36 ...
output:
1948646
result:
ok 1 number(s): "1948646"
Test #26:
score: 0
Accepted
time: 81ms
memory: 173636kb
input:
200000 200000 200000 35797 200000 167458 200000 39806 200000 88546 200000 165714 200000 117657 200000 168133 200000 81774 200000 140104 200000 176682 200000 188272 200000 177500 200000 2880 200000 76995 200000 124498 200000 198682 200000 25866 200000 189009 200000 187674 200000 189285 200000 63188 2...
output:
7999880000400000
result:
ok 1 number(s): "7999880000400000"
Test #27:
score: 0
Accepted
time: 1069ms
memory: 116072kb
input:
200000 200000 200000 89814 1 116496 1 118564 1 464 1 126025 1 89571 2 197312 2 9858 2 85590 5 65225 8 148868 10 129076 11 103169 11 73239 12 142418 12 116100 13 46404 13 63424 14 66422 17 146171 17 145610 17 56698 17 180250 18 148868 19 129755 19 139751 20 154900 20 186629 21 62893 21 85249 21 71296...
output:
1188676324
result:
ok 1 number(s): "1188676324"
Test #28:
score: 0
Accepted
time: 89ms
memory: 152372kb
input:
199995 199993 3 139758 1 105092 1 116815 1 155810 1 117619 1 32962 1 165462 1 75347 1 58622 1 83533 1 198966 1 158315 1 157783 1 178123 1 56804 1 22718 1 135200 1 189569 1 5238 1 160413 1 85655 1 23921 1 83704 1 106882 1 38863 1 105112 1 65676 1 113998 1 29107 1 167276 1 124461 1 173183 1 110513 1 1...
output:
1434302202794094
result:
ok 1 number(s): "1434302202794094"
Test #29:
score: 0
Accepted
time: 62ms
memory: 129412kb
input:
197710 51514 199999 18607 199976 11648 199976 48300 199976 36251 199976 20168 199976 39939 199976 49063 199976 40145 199976 15002 199976 17993 199976 14752 199976 19829 199976 44936 199976 42612 199976 16625 199976 2013 199976 41690 199976 11181 199976 45441 199976 25242 199976 15854 199976 2123 199...
output:
136662051779304
result:
ok 1 number(s): "136662051779304"
Test #30:
score: 0
Accepted
time: 414ms
memory: 115432kb
input:
200000 74614 200000 22630 1 27567 1 60945 1 15633 1 3882 1 47524 1 45604 1 36741 1 63680 1 66142 1 60811 1 45697 1 9511 1 25248 1 35203 1 40929 1 35698 1 13641 1 46717 1 11294 1 54187 1 5471 1 25873 1 25207 1 20331 1 61719 1 68557 1 69570 1 61108 1 26112 1 1772 1 56132 1 11287 1 6368 1 13528 1 63069...
output:
135796230
result:
ok 1 number(s): "135796230"
Test #31:
score: 0
Accepted
time: 170ms
memory: 128696kb
input:
200000 31247 200000 10554 1 24385 1 9400 1 21999 1 24385 1 10874 1 16922 1 14381 1 16922 1 5492 1 5901 1 21999 1 16922 1 21999 1 16922 1 9400 1 5901 1 10337 1 9400 1 10337 1 21999 1 23957 1 16922 1 10874 1 5901 1 4181 1 16922 1 9400 1 5901 1 9400 1 5901 1 4181 1 10874 1 26165 1 10874 1 24385 1 10337...
output:
17606590183202
result:
ok 1 number(s): "17606590183202"
Test #32:
score: 0
Accepted
time: 1422ms
memory: 110544kb
input:
200000 515 200000 454 1 477 1 15 1 188 1 394 1 20 1 513 1 378 1 509 1 322 1 392 1 215 1 473 1 465 1 367 1 155 1 265 1 239 1 264 1 511 1 300 1 8 1 86 1 17 1 96 1 84 1 50 1 440 1 89 1 336 1 55 1 144 1 25 1 235 1 59 1 182 1 296 1 227 1 154 1 233 1 289 1 246 1 270 1 200 1 418 1 311 1 474 1 206 1 338 1 4...
output:
135796230
result:
ok 1 number(s): "135796230"
Test #33:
score: 0
Accepted
time: 536ms
memory: 115412kb
input:
200000 200000 200000 119672 1 172761 1 158391 3 157543 4 113113 7 3794 10 193802 10 193228 13 190363 14 78983 14 157724 14 81793 15 142847 15 66734 16 60442 17 73056 17 66734 18 199261 19 86256 19 107766 23 87752 24 101826 26 135559 26 39392 27 93143 28 49876 28 123967 29 136767 31 54217 32 21378 33...
output:
294844949
result:
ok 1 number(s): "294844949"
Test #34:
score: 0
Accepted
time: 31ms
memory: 114428kb
input:
199995 3 199993 1 2 1 3 3 4 1 4 2 4 1 4 3 5 1 5 2 5 2 7 1 8 2 9 3 9 2 10 1 13 1 15 3 15 1 17 1 20 2 21 2 22 2 29 2 30 1 32 2 33 2 33 2 33 1 34 1 34 2 37 3 39 3 40 1 41 2 47 3 47 2 48 3 48 1 49 1 49 3 50 3 51 2 52 3 52 2 56 3 56 2 58 2 59 2 60 3 60 1 60 3 61 3 63 2 64 1 64 3 65 1 67 3 67 2 68 3 68 1 ...
output:
6
result:
ok 1 number(s): "6"
Extra Test:
score: 0
Extra Test Passed