QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #133052 | #6630. Triangle Collection | MtSaka# | 0 | 141ms | 3792kb | C++20 | 1.7kb | 2023-08-01 14:08:09 | 2024-07-04 01:05:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,q;
cin>>n>>q;
if(n>2000||q>2000)return 0;
vector<int>c(n);
for(auto&e:c)cin>>e;
while(q--){
//debug(q);
int l,d;cin>>l>>d;
c[l-1]+=d;
map<int,int>mp;
for(int i=0;i<n;i++)if(c[i]&1)mp[i]=1;
int idx=0;
auto cnt=c;
long long ans=0;
for(auto&e:cnt)e/=2;
for(int i=n-1;i>=0;i--){
while(cnt[i]&&mp.size()){
auto it=mp.rbegin();
if(it->first>=2*i+1){
mp.erase(--mp.end());
}
else{
if(cnt[i]<it->second){
mp[it->first]-=cnt[i];
ans+=cnt[i];
cnt[i]=0;
}
else{
cnt[i]-=it->second;
ans+=it->second;
mp.erase(--mp.end());
}
}
}
while(cnt[i]&&idx<i){
if(cnt[i]>2*cnt[idx]){
cnt[i]-=2*cnt[idx];
ans+=2*cnt[idx];
cnt[idx]=0;
idx++;
}
else{
cnt[idx]-=(cnt[i]+1)/2;
ans+=cnt[i];
cnt[i]=0;
if(cnt[i]&1)mp[idx]++;
}
}
if(idx==i&&cnt[i]){
int x=(cnt[i]+2)/3;
ans+=cnt[i]-x;
mp[i]+=2*x-(cnt[i]-x);
}
}
cout<<ans<<endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 3576kb
input:
1 23 1485 1 -12 1 -30 1 -20 1 6 1 24 1 5 1 31 1 14 1 -34 1 -22 1 -45 1 37 1 46 1 9 1 22 1 -9 1 9 1 -46 1 -47 1 39 1 36 1 -36 1 50
output:
491 481 474 476 484 486 496 501 489 482 467 479 495 498 505 502 505 490 474 487 499 487 504
result:
ok 23 numbers
Test #2:
score: -5
Wrong Answer
time: 0ms
memory: 3792kb
input:
12 1 13 79 59 21 32 13 85 40 74 15 49 56 3 31
output:
188
result:
wrong answer 1st numbers differ - expected: '189', found: '188'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 112ms
memory: 3636kb
input:
1999 2000 1 1 1 1 0 2 0 2 1 0 2 1 2 2 2 1 2 0 0 1 2 2 0 1 0 1 0 2 0 0 2 1 1 1 1 0 1 2 1 2 1 1 1 1 1 0 2 2 0 2 1 1 2 0 0 2 0 0 2 1 2 0 0 1 1 2 0 2 2 2 1 2 0 2 1 2 0 1 2 2 2 1 1 2 1 1 1 1 0 0 1 1 0 1 2 1 0 0 2 0 2 2 2 0 1 1 2 0 0 1 0 0 2 1 2 1 2 0 1 1 2 2 0 0 1 2 2 1 2 1 2 2 2 0 0 1 1 2 1 1 2 2 2 2 2 ...
output:
660 660 660 661 661 661 661 660 660 660 660 661 662 662 663 663 662 661 662 662 661 660 661 660 660 660 661 661 661 661 662 661 661 660 661 660 659 658 658 659 659 658 659 660 660 660 660 660 660 659 659 659 659 659 659 659 659 660 659 658 658 658 658 657 657 657 658 657 656 657 657 657 656 656 655 ...
result:
wrong answer 1664th numbers differ - expected: '666', found: '665'
Subtask #4:
score: 0
Wrong Answer
Test #35:
score: 0
Wrong Answer
time: 141ms
memory: 3624kb
input:
2000 1999 0 1 0 3 0 1 0 0 0 0 0 0 0 2 0 0 0 0 3 1 1 0 2 0 0 3 0 0 0 0 0 4 0 0 1 0 1 0 0 0 0 1 2 1 0 0 0 0 7 0 1 3 1 0 1 1 0 3 2 1 0 1 1 3 3 1 0 2 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 1 2 3 0 1 0 3 3 0 0 0 0 1 0 1 2 0 0 2 2 0 1 2 1 2 0 0 0 1 1 0 1 2 0 0 0 0 2 0 5 0 0 0 0 0 1 0 0 2 0 1 2 0 1 0 0 0 2 0 ...
output:
665 666 665 666 665 666 665 666 665 665 664 665 664 664 664 664 664 665 664 664 664 664 664 665 665 666 665 666 665 665 665 666 665 666 665 666 665 665 665 666 666 666 666 666 665 665 665 665 665 665 665 665 665 665 665 665 665 665 665 665 665 666 666 666 666 666 665 665 665 666 665 666 665 665 665 ...
result:
wrong answer 1st numbers differ - expected: '666', found: '665'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%