QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742105#7622. Yet Another CoffeeCarucao#WA 1ms9712kbC++201.6kb2024-11-13 15:52:092024-11-13 15:52:11

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 15:52:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9712kb
  • [2024-11-13 15:52:09]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a[N],c[N],pre[N];
struct adc
{
	int x,id;
}b[N];
pair<int,int> minn[N<<2];
bool cmp(adc a,adc b)
{
	if(a.x==b.x) return a.id<b.id;
	return a.x<b.x;
}
void update(int l,int r,int node,int pos,int v)
{
	if(l==r)
	{
		minn[node]=make_pair(v,l);
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) update(l,mid,node<<1,pos,v);
	else update(mid+1,r,node<<1|1,pos,v);
	minn[node]=min(minn[node<<1],minn[node<<1|1]);
}
pair<int,int> query(int l,int r,int node,int L,int R)
{
	if(L<=l&&r<=R) return minn[node];
	int mid=l+r>>1;
	pair<int,int> ll=make_pair(1e15,0), rr=make_pair(1e15,0);
	if(L<=mid) ll=query(l,mid,node<<1,L,R);
	if(R>mid) rr=query(mid+1,r,node<<1|1,L,R);
	return min(ll,rr);
}
void work()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i],c[i]=0,b[i]={a[i],i};
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;++i) pre[i]=pre[i-1]+b[i].x;
    int sum=0;
    for(int i=1;i<=m;++i)
    {
    	int r,w;
    	cin>>r>>w;
    	c[r+1]+=w;
    	sum+=w;
	}
	for(int i=1;i<=n;++i) 
	{
		sum-=c[i];
		a[i]-=sum;
	}
	for(int i=1;i<=n;++i) update(1,n,1,i,a[b[i].id]);
	for(int i=1;i<=n;++i)
	{
	    pair<int,int> u=query(1,n,1,1,i);
	    pair<int,int> v;
		if(i<n) v=query(1,n,1,i+1,n);
		else v=make_pair(1e15,0);
		int res=u.first+pre[i]-b[u.second].x;
		int tmp=v.first+pre[i-1];
		cout<<min(res,tmp)<<" ";
	}
	cout<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    for(;T;--T)
      work();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9712kb

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: 0ms
memory: 9712kb

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: 7724kb

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: 9712kb

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 1079767658 1379641751 1699842679 2101752988 2494614073 2893464217 3314183134 3796146073 4299654352 4911763702 
335919368 705602908 
146524143 438492672 
-3870833640 -3817930784 -3749728771 -3627446160 -3460387488 -321...

result:

wrong answer 12th numbers differ - expected: '2043562112', found: '2101752988'