QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#303327 | #6692. Building Company | ship2077 | WA | 37ms | 25776kb | C++14 | 1.5kb | 2024-01-12 07:09:20 | 2024-01-12 07:09:21 |
Judging History
answer
#include<bits/stdc++.h>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
constexpr int M=2e5+5;ll add[M];queue<pair<int,int>>q;
vector<pair<int,int>>pos[M],qry[M],upd[M];
int n,m,k,num,ans,a[M],b[M],lsh[M],buc[M],head[M];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
int main(){ n=read();
for (int i=1;i<=n;i++) a[i]=read(),b[i]=read(),lsh[++num]=a[i];
m=read(); for (int i=1;i<=m;i++){
k=read();while (k--) qry[i].push_back({read(),read()}),lsh[++num]=qry[i].back().fir;
k=read();while (k--) upd[i].push_back({read(),read()}),lsh[++num]=upd[i].back().fir;
}
sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
for (int i=1;i<=n;i++) a[i]=lower_bound(lsh+1,lsh+num+1,a[i])-lsh;
for (int i=1;i<=m;i++){
for (auto &[x,y]:qry[i]) x=lower_bound(lsh+1,lsh+num+1,x)-lsh,pos[x].push_back({y,i}),buc[i]++;
for (auto &[x,y]:upd[i]) x=lower_bound(lsh+1,lsh+num+1,x)-lsh;
}
for (int i=1;i<=num;i++) sort(pos[i].begin(),pos[i].end());
for (int i=1;i<=n;i++) q.push({a[i],b[i]});
for (int i=1;i<=m;i++)
if (!buc[i]){ ans++;
for (auto x:upd[i])
q.push(x);
}
while (!q.empty()){
pair<int,int> x=q.front();q.pop();add[x.fir]+=x.sec;
while (head[x.fir]<pos[x.fir].size()&&pos[x.fir][head[x.fir]].fir<=add[x.fir]){
int tmp=pos[x.fir][head[x.fir]].sec;
if (!--buc[tmp]){ ans++;
for (auto x:upd[tmp]) q.push(x);
}
head[x.fir]++;
}
}
printf("%d\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 20412kb
input:
2 2 1 1 2 5 1 3 1 0 2 1 1 2 1 2 3 2 2 1 3 1 5 2 3 3 4 1 2 5 3 2 1 1 1 3 4 1 1 3 0 1 3 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 20084kb
input:
3 610031727 590328742 816793299 18485566 654221125 47823436 10 3 610031727 224714165 816793299 491951703 654221125 593479446 1 610031727 538596643 1 610031727 551036304 3 816793299 262985484 610031727 52580932 654221125 424397787 1 654221125 889197190 3 654221125 126924193 610031727 963399336 816793...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 5ms
memory: 20588kb
input:
10 720543365 814021419 777649737 273919247 339754140 472967790 545693058 298289557 949226024 176807538 267294560 819212220 337794335 504610276 137418995 614590802 632556957 783062334 587607535 115519693 100 5 949226024 327424834 777649737 117746775 137418995 152960310 720543365 423301366 267294560 4...
output:
100
result:
ok 1 number(s): "100"
Test #4:
score: 0
Accepted
time: 0ms
memory: 22252kb
input:
33 598906111 952747266 214206082 308472115 773699301 71970369 334282917 266176016 861160505 745480638 397625705 130382274 75028923 106125916 739923352 754152044 493886549 212094717 352869179 727757279 697376464 343501623 916521518 80952344 90959088 722016125 286878647 329186592 770901193 30277256 92...
output:
100
result:
ok 1 number(s): "100"
Test #5:
score: 0
Accepted
time: 35ms
memory: 25776kb
input:
380 562284409 583959039 705240193 694592025 91058796 151967354 775570098 571811699 457579493 117213529 684664737 33837962 60865228 186423701 316573783 868301583 744570505 934432338 790259030 364551324 145817136 961903964 737096543 759008968 865899868 681823261 273067044 247683791 186025557 756452454...
output:
992
result:
ok 1 number(s): "992"
Test #6:
score: 0
Accepted
time: 33ms
memory: 24812kb
input:
3 293768553 273246573 143991316 507392430 358993111 920969223 100000 4 46041344 835899600 358993111 994240598 293768553 484011013 143991316 777828426 0 0 0 5 143991316 794586365 46041344 405796774 722229657 508855404 293768553 369514799 358993111 4028509 3 143991316 258883273 358993111 986311988 460...
output:
100000
result:
ok 1 number(s): "100000"
Test #7:
score: 0
Accepted
time: 30ms
memory: 25616kb
input:
2 961288235 443865989 396580494 578798612 100000 34 421946957 299618245 78391742 196256544 561711742 14201606 657355823 12773731 46715022 916005233 307668801 286702191 158073396 813604706 961288235 632264049 137129358 649927330 69336461 331852084 768586802 142594294 800292046 696090805 674814060 644...
output:
100000
result:
ok 1 number(s): "100000"
Test #8:
score: -100
Wrong Answer
time: 37ms
memory: 23804kb
input:
118 302362725 748141404 107046714 926152648 886186708 125758872 452810643 243408822 807034444 7712734 770559271 84899208 578273022 102765302 276241387 922873983 952906448 582532305 67022370 663519345 379715473 619080027 481503038 207664807 267966322 105276315 179029836 537064295 838588147 386785169 ...
output:
99997
result:
wrong answer 1st numbers differ - expected: '99787', found: '99997'