QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#405104#8229. 栈dingdingtang11514#0 32ms7884kbC++143.1kb2024-05-05 11:22:462024-05-05 11:22:46

Judging History

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

  • [2024-05-05 11:22:46]
  • 评测
  • 测评结果:0
  • 用时:32ms
  • 内存:7884kb
  • [2024-05-05 11:22:46]
  • 提交

answer

#include <iostream>
#include <cstring> 
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
// #include <bits/stdc++.h>

#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define Grf(it,u,to) for(int it=he[u],to;(to=e[it],it);it=nxt[it]) 
#define In __inline 
#define OP operator
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Mine {
	// mt19937_64 wql(514);
	In int read() {
		ll x=1,a=0;
		char ch=getchar();
		while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
		while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
		return a*x;
	} const int N=1e5+100;
	int n,m;
	namespace S0 {
		struct stk {
			int sts[5005],stv[5005],tot;
			void push(int val,int sum) {sts[++tot]=sum,stv[tot]=val;}
			void pp(int cnt) {
				while(tot && sts[tot]<=cnt) cnt-=sts[tot--];
				if(tot) sts[tot]-=cnt;
			} In int get(int p) {
				int ret=0,i=1; while(i<=tot && p>=sts[i]) {
					p-=sts[i];ret+=sts[i]*stv[i];i++;
				} if(i<=tot) ret+=stv[i]*p;
				return ret;
			} In int get(int l,int r){
				return get(r)-get(l-1);
			} void print() {
				For(i,1,tot) printf("%lld ",sts[i]);
				puts("");
			}
		} mp[5005];
		void solve0() {
			while(m--) {
				// printf("%d :\n",m);
				int opt=read(); if(opt==1) {
					int l=read(),r=read(),x=read(),y=read();
					For(i,l,r) mp[i].push(y,x);
				} else if(opt==2) {
					int l=read(),r=read(),x=read();
					For(i,l,r) mp[i].pp(x);
				} else {
					int x=read(),l=read(),r=read();
					printf("%lld\n",mp[x].get(l,r));
				} //For(i,1,n) mp[i].print();
				// puts("");
			}
		}
	} namespace S1 {
		struct node{
			int x=0,y=0;   ///   a_i = max ( x , a_i + y )
		} tr[N<<2];
		void pushdown(int u) {
			int X=tr[u].x,Y=tr[u].y;
			tr[u<<1].x+=X,tr[u<<1|1].x+=X;
			tr[u<<1].y=max(tr[u<<1].y+X,Y);
			tr[u<<1|1].y=max(tr[u<<1|1].y+X,Y);
			tr[u].x=tr[u].y=0;
		}
		void mdf(int ql,int qr,int val,int u=1,int l=1,int r=n) {
			if(ql<=l && r<=qr) tr[u].x+=val,tr[u].y=0;
			else { int mid=(l+r)>>1; pushdown(u);
				if(ql<=mid) mdf(ql,qr,val,u<<1,l,mid);
				if(mid<qr) mdf(ql,qr,val,u<<1|1,mid+1,r);
			}
		} int ask(int pos,int u=1,int l=1,int r=n) {
			if(l==r) return max(0+tr[u].x,tr[u].y);
			int mid=(l+r)>>1; pushdown(u);
			if(pos<=mid) return ask(pos,u<<1,l,mid);
			return ask(pos,u<<1|1,mid+1,r);
		}
		void solve1() {
			while(m--) {
				// printf("%d :\n",m);
				int opt=read(); if(opt==1) {
					int l=read(),r=read(),x=read(),y=read();
					mdf(l,r,x);
				} else if(opt==2) {
					int l=read(),r=read(),x=read();
					mdf(l,r,-x);
				} else {
					int x=read(),l=read(),r=read();
					int siz=ask(x); 
					printf("%lld\n",min(siz,r)-min(siz,l-1));
				} //For(i,1,n) printf("%lld ",ask(i));
				// putsa("");
			}
		}
	}
	signed main() {
		n=read(),m=read();
		// if(n<=5000 && m<=5000) S0::solve0();
		// else S1::solve1();
		
		S1::solve1();
		
		
		
		return 0;
	}
}signed main() {
	// freopen("homework.in","r",stdin);
	// freopen("homework.out","w",stdout);
	return Mine::main();
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 4036kb

input:

4907 4910
2 763 3330 1
3 307 1 1
1 2262 3430 22699 89397
1 1915 4000 51541 67587
2 212 2990 9763
2 1086 2162 1
2 1813 4496 16760
1 51 2796 68005 99390
1 1267 1519 74236 66178
3 1768 23808 54314
2 900 4122 27758
3 3287 17350 28989
2 3277 4024 3633
2 444 4866 1
2 353 4219 1061
1 987 3141 99906 17320
2...

output:

0
30507
11640
5275
3437
0
25911
0
1146
0
0
0
0
13060
0
7846
0
130450
0
22042
101132
24302
17557
2850
162970
0
9062
0
7845
85303
108469
0
0
45427
130254
48754
0
0
51519
11465
7399
0
81716
53555
0
0
14394
0
4218
0
11391
3958
86292
0
35736
5369
0
0
0
49479
1179
4534
16295
15596
18833
42042
17557
10253
...

result:

wrong answer 2nd numbers differ - expected: '3032090730', found: '30507'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 32ms
memory: 7832kb

input:

99999 99998
1 5026 18575 27178 90423
3 30623 1 1
3 76936 1 1
1 77021 95683 84664 24734
1 46085 74886 40512 11266
3 5048 8594 22468
1 53318 77721 97151 70784
1 70645 91192 37556 13013
1 56752 56940 91812 62887
1 7928 34576 87339 69404
3 74875 32807 100970
3 22338 17221 25771
3 21421 20602 57957
3 717...

output:

0
0
13875
68164
8551
37356
51678
78688
9772
17674
28663
11002
102350
18755
36993
229473
61114
309657
445575
67332
280040
41468
565383
14241
245087
151356
35296
139339
108738
174373
21036
290401
205700
405809
35460
43749
209279
494612
42184
624800
245616
672241
71368
774313
1002309
259392
236613
8906...

result:

wrong answer 3rd numbers differ - expected: '1254619125', found: '13875'

Subtask #3:

score: 0
Wrong Answer

Test #12:

score: 0
Wrong Answer
time: 24ms
memory: 7844kb

input:

100000 99993
1 47773 70467 16065 1
2 52349 78446 2304
3 40821 1 1
1 40216 93069 78144 1
1 41089 43671 76025 1
2 35263 68629 31066
3 79881 13534 57327
3 5556 1 1
2 21962 38192 1
1 664 58116 9417 1
3 28089 6039 7989
2 88500 90302 9946
3 63215 49410 60770
2 11069 89527 57581
2 70303 97603 12363
1 3420 ...

output:

0
43794
0
1951
11361
129
898
29245
7969
0
34972
16405
59952
123666
24537
68209
34537
0
32225
32066
0
26333
16824
96178
14285
245288
57614
1602
114570
61935
4068
65762
17609
152949
26099
179359
250368
2323
183349
125791
17414
61871
0
0
0
183297
23029
54464
0
26259
204595
35604
0
0
18437
0
0
0
138046
...

result:

wrong answer 10th numbers differ - expected: '1947', found: '0'

Subtask #4:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 28ms
memory: 7884kb

input:

99999 99996
3 77889 1 10000000000
1 6316 86327 89644 386
3 9260 1 10000000000
2 2603 47234 69717
2 20260 73011 19290
2 62477 81233 26127
1 50140 68508 37004 98794
2 14449 22788 16063
1 43860 84932 50375 21777
1 67345 94584 28202 66610
2 661 68654 1
1 14411 94422 82738 61196
1 16563 94416 4920 38408
...

output:

0
89644
0
0
586692
52542
0
77150
77150
105774
77150
0
0
63627
107367
71244
0
220294
68770
41680
58519
108806
0
84171
37494
0
0
262388
189704
0
183158
0
330620
266786
200713
6281
292978
0
99905
0
0
0
35935
170639
48307
152865
0
114736
0
0
0
0
102049
0
92045
270432
205670
0
0
81804
271323
35933
22901
...

result:

wrong answer 2nd numbers differ - expected: '34602584', found: '89644'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%