QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#574107 | #7622. Yet Another Coffee | rerebornzhou | WA | 6ms | 40980kb | C++20 | 2.7kb | 2024-09-18 20:48:17 | 2024-09-18 20:48:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
#define ull unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
const int N=2e5+10;
// const int INF=1e18;
int n,m;
int a[N],b[N];
int ls(int x) {return x<<1;};
int rs(int x) {return x<<1|1;};
struct quan{
int r,w;
}q[N];
struct TreeNode{
int l,r;
int lazy;
int pos;
int minn=1e18;
}tree[N*4];
void pushup(int t){
if(tree[ls(t)].minn<=tree[rs(t)].minn){
tree[t].minn=tree[ls(t)].minn;
tree[t].pos=tree[ls(t)].pos;
}
else if(tree[ls(t)].minn>tree[rs(t)].minn){
tree[t].minn=tree[rs(t)].minn;
tree[t].pos=tree[rs(t)].pos;
}
}
void pushdown(int t){
tree[ls(t)].lazy+=tree[t].lazy;
tree[rs(t)].lazy+=tree[t].lazy;
tree[ls(t)].minn+=tree[t].lazy;
tree[rs(t)].minn+=tree[t].lazy;
tree[t].lazy=0;
}
void build(int t,int l,int r){
tree[t].l=l;
tree[t].r=r;
tree[t].minn=1e18;
tree[t].lazy=0;
if(l==r) {
tree[t].pos=l;
tree[t].minn=a[l];
return;
}
int mid=l+r>>1;
build(ls(t),l,mid);
build(rs(t),mid+1,r);
pushup(t);
}
void modify(int t,int l,int r,int p){
if(l<=tree[t].l&&tree[t].r<=r){
tree[t].lazy+=p;
tree[t].minn+=p;
return;
}
pushdown(t);
int mid=tree[t].l+tree[t].r>>1;
if(l<=mid) modify(ls(t),l,r,p);
if(r>mid) modify(rs(t),l,r,p);
pushup(t);
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) b[i]=0;
for(int i=1;i<=m;i++){
cin>>q[i].r>>q[i].w;
// cerr<<q[i].r<<" "<<q[i].w<<"\n";
b[1]-=q[i].w;
b[q[i].r+1]+=q[i].w;
}
for(int i=1;i<=n;i++) b[i]+=b[i-1];
for(int i=1;i<=n;i++){
a[i]+=b[i];
// cout<<a[i]<<" \n"[i==n];
}
build(1,1,n);
sort(q+1,q+1+m,[](quan a,quan b){ return a.r<b.r;});
int pp=m;
int ans=0;
vector<int> vt;
for(int i=1;i<=n;i++){
ans+=tree[1].minn;
vt.push_back(ans);
// cerr<<"pos= "<<tree[1].pos<<"\n";
modify(1,tree[1].pos,tree[1].pos,1e18);
// cerr<<i<<" "<<q[pp].r<<" "<<tree[1].pos<<"\n";
while(pp&&q[pp].r>=tree[1].pos){
// cerr<<"modify "<<i<<" "<<q[pp].r<<" "<<q[pp].w<<"\n";
modify(1,1,q[pp].r,q[pp].w);
pp--;
}
}
for(auto t:vt){
cout<<t<<" ";
}
cout<<"\n";
}
signed main(){
IOS
int _=1;
cin>>_;
while(_--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 40980kb
input:
5 10 14 17 37 59 65 53 73 68 177 160 111 10 177 5 193 2 30 3 63 2 339 3 263 5 178 2 190 9 23 10 328 10 200 9 8 3 391 6 230 12 9 152 306 86 88 324 59 18 14 42 260 304 55 3 50 2 170 1 252 7 811 1 713 7 215 10 201 4 926 8 319 19 20 182 74 180 201 326 243 195 31 170 263 284 233 48 166 272 281 179 116 31...
output:
-2596 -2559 -2506 -2447 -2382 -2314 -2241 -2130 -1970 -1793 -3505 -3491 -3473 -3431 -3376 -3317 -3231 -3143 -2883 -2579 -2273 -1949 -6527 -6496 -6448 -6374 -6258 -6092 -5922 -5743 -5563 -5368 -5167 -4934 -4691 -4428 -4156 -3875 -3591 -3272 -2946 -3219 -2987 -2572 -2140 -1707 -1238 -768 -274 243 1...
result:
ok 70 numbers
Test #2:
score: 0
Accepted
time: 6ms
memory: 40896kb
input:
2 5 2 1 2 3 4 5 3 1 4 2 7 3 4 3 1 10 3 8 6 4 9 3 8 4 5
output:
-2 0 3 7 12 -21 -18 -15 -11 -5 3 13
result:
ok 12 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 40232kb
input:
8 1 0 72916 9 11 130289 240521 653024 625847 679075 529899 486802 540872 353600 2 5400 2 257841 6 48161 3 71484 9 156788 3 181910 4 45589 6 210869 5 70426 9 87059 5 115764 8 7 634608 412120 360938 425426 825551 138578 678304 747502 2 235317 4 281859 5 553042 8 295615 8 32014 8 755313 4 439284 19 10 ...
output:
72916 -1121002 -880481 -526881 -40079 489820 1030692 1656539 2309563 2988638 -2180324 -2041746 -1680808 -1255382 -620774 57530 805032 1630583 -1025384 -1022941 -1018403 -1013731 -1006580 -998875 -987675 -970496 -953098 -932654 -909692 -886331 -862054 -835158 -807901 -779123 -747157 -713222 -67928...
result:
ok 85 numbers
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 40640kb
input:
5 18 24 561699155 345484852 420718917 108291879 553918474 392861085 299874093 28528146 248352314 398850144 248444258 89834833 251398697 101739017 240342391 320200928 481962939 343719433 5 354704 6 9355942 7 7098134 16 38746862 15 35848885 14 42058214 15 18411581 9 23207206 18 19518309 14 20707458 13...
output:
-416165974 -387637828 -297802995 -196063978 44278413 292630727 541074985 792473682 1092347775 1412548703 1756268136 2101752988 2494614073 2893464217 3314183134 3796146073 4350064547 4911763702 335919368 705602908 146524143 438492672 -3870833640 -3817930784 -3749728771 -3627446160 -3460387488 -321...
result:
wrong answer 9th numbers differ - expected: '1079767658', found: '1092347775'