QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#405113#8229. 栈dingdingtang11514#34 131ms49664kbC++143.2kb2024-05-05 11:28:582024-05-05 11:29:00

Judging History

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

  • [2024-05-05 11:29:00]
  • 评测
  • 测评结果:34
  • 用时:131ms
  • 内存:49664kb
  • [2024-05-05 11:28:58]
  • 提交

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 pushtag(int u,int x,int y) {
			tr[u].x+=x,tr[u].y=max(tr[u].y+x,y);
		}
		void pushdown(int u) {
			int X=tr[u].x,Y=tr[u].y;
			pushtag(u<<1,X,Y);pushtag(u<<1|1,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) pushtag(u,val,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));
				 // puts("");
			}
		}
	}
	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();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 18
Accepted

Test #1:

score: 18
Accepted
time: 74ms
memory: 46248kb

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
3032090730
903396180
471569175
200648623
98486697
647114751
123945
50793012
61782451
0
0
0
762429740
321140700
871619914
536311874
5361094892
0
1792521566
6640518748
2415375780
249435711
225987900
5250788038
1145132507
140071334
0
118545795
3086405469
5646099271
84280112
1232466642
4992966775
7968...

result:

ok 1622 numbers

Test #2:

score: 18
Accepted
time: 89ms
memory: 45164kb

input:

4992 4958
2 2965 3892 1
3 2141 1 1
3 4963 1 1
3 2298 1 1
3 2236 1 1
1 3393 4668 65533 8224
1 884 2343 86158 41289
3 4617 12174 63763
2 898 4236 44143
2 2860 4246 1
2 2696 3014 1
2 496 1635 15779
3 2230 8262 39805
2 3287 3627 5350
2 3443 4900 19874
1 535 1622 26926 88406
1 3272 3747 94290 19081
2 812...

output:

0
0
0
0
424276160
1302420216
0
393525459
0
188112684
0
38587680
696225296
717180100
2193537294
297696966
0
0
0
124461621
26876032
1609925499
0
3681040200
51602516
1502016
0
8636592
1138256753
196684293
0
16126264
959145423
58640451
1945754097
2949696960
0
3577791360
2029416288
2361290004
5882833609
...

result:

ok 1597 numbers

Test #3:

score: 18
Accepted
time: 89ms
memory: 46076kb

input:

4980 4984
1 183 4891 75896 45281
2 767 3528 1367
3 2313 45535 49112
2 529 4006 1568
2 2114 2971 3819
3 3237 30655 31381
1 2074 2176 51631 35339
3 1602 95 16082
2 1340 3727 9249
2 105 1907 11928
3 2461 15189 33999
2 1450 1956 4721
1 700 4760 3043 92859
2 329 2992 6515
3 1295 10832 40486
2 3477 4447 8...

output:

162015418
32919287
723952628
851780891
1342808055
38307726
4701651115
903944603
240532672
652952020
1168430924
2253203546
3542990917
5872603595
305017015
657095398
25321688
1834305604
0
256832266
2732654054
1757936801
1158797383
656866283
3470700279
694675745
1042863834
76284096
6705704850
475899629...

result:

ok 1645 numbers

Test #4:

score: 18
Accepted
time: 87ms
memory: 46160kb

input:

4976 4948
2 858 1218 1
1 780 1528 70910 12344
1 681 4398 25997 59182
1 4564 4692 72420 96925
1 1124 2604 98159 98651
3 4734 1 1
2 1921 3430 3373
1 3805 3909 56118 23383
2 1471 2065 23679
2 1052 1154 30740
1 1098 2180 13716 29728
1 1094 3585 2073 93894
1 2024 4201 39023 1713
3 1571 21453 96893
3 1297...

output:

0
7262943486
185110624
53327400
957813600
383014415
1539405803
896522316
1454164560
7158196459
479198625
1943839360
1189657450
23355822139
2684778350
183742084
6400082784
2310401225
2082631008
5644811789
1875949890
3185562597
7185156304
3147144197
1588457333
676240200
1122598010
8758314557
100699296...

result:

ok 1663 numbers

Test #5:

score: 18
Accepted
time: 131ms
memory: 49664kb

input:

4944 4934
1 468 4845 87517 63656
3 4756 22899 79177
1 761 1054 45331 86403
1 24 2806 46189 11490
1 2602 4446 12528 14317
3 2601 51537 65051
1 1502 3573 79699 84830
3 1998 35405 151264
1 2400 4041 95071 83748
1 2050 3772 23643 53614
3 2261 51072 236192
2 1317 1908 6197
2 949 2543 30190
1 1457 4573 33...

output:

3582496024
860310840
5337461878
10833286574
1397502876
3735482073
4207877274
17671620
10854427218
1484917319
5462491276
1497165465
1453546510
1672688712
1158344316
1014734250
3797802047
15668090927
14634073116
32337553147
2159971110
12088416736
90924880
1410366456
13829776128
12126485158
18393654569...

result:

ok 829 numbers

Subtask #2:

score: 0
Wrong Answer

Test #6:

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

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: 16
Accepted

Test #12:

score: 16
Accepted
time: 34ms
memory: 7940kb

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
1947
34972
16405
59952
123666
24537
68209
34537
0
32225
37527
0
31810
16824
96178
14285
300941
57614
1602
129470
61935
4068
114182
17609
152949
26099
179359
250368
4796
183349
125791
17414
61871
42058
0
2698
183297
23029
54464
0
26259
204595
35604
0
0
18437
29...

result:

ok 33281 numbers

Test #13:

score: 16
Accepted
time: 31ms
memory: 7892kb

input:

100000 99999
3 11279 1 1
1 21196 82827 47041 1
2 58608 97529 1
2 22065 32528 37154
1 2138 16260 96858 1
1 25755 42875 82334 1
1 31799 48594 28327 1
3 58271 16371 33060
1 9407 50398 53680 1
2 40505 54132 176725
2 4626 22919 41250
2 28476 63110 133245
2 501 87564 1
2 5927 27401 96494
2 27254 64078 1
2...

output:

0
16690
27551
1442
4671
0
35160
4953
1559
3430
1768
0
0
11628
0
0
2495
13673
0
0
162093
135864
330
17312
0
29074
0
0
0
33641
51926
7051
0
0
42277
0
44110
543
12418
51322
9338
89794
9387
44052
43969
170272
42203
209676
5275
15969
11537
29757
26609
8288
33600
0
21384
48804
75598
11624
67508
10170
1751...

result:

ok 33467 numbers

Test #14:

score: 16
Accepted
time: 26ms
memory: 7920kb

input:

99993 99998
3 67041 1 1
3 6929 1 1
2 17524 32038 1
2 61604 73005 1
3 89616 1 1
2 40031 62338 1
3 58255 1 1
1 13009 67563 20939 1
1 73959 97229 47418 1
2 60834 61638 3740
2 29078 66369 1909
3 20355 4984 7284
2 75885 86625 3998
1 58692 90189 3242 1
3 99600 1 1
1 4102 8018 16478 1
3 53676 3918 8517
3 6...

output:

0
0
0
0
2301
0
4600
1472
56471
13213
0
143912
24988
0
59240
0
0
65385
5137
154745
70944
42704
209563
9676
121308
24627
52979
49278
37462
16444
0
1611
409040
392695
111628
265718
65783
55560
11142
45479
32621
118811
0
27594
239805
284844
19955
220309
8044
161759
1982
53200
41530
102413
43466
28624
17...

result:

ok 33389 numbers

Test #15:

score: 16
Accepted
time: 33ms
memory: 7760kb

input:

99991 99996
1 47657 83825 20467 1
2 18475 94316 1
1 45137 56194 42134 1
2 62287 64784 3656
1 34371 82222 66403 1
2 26982 76957 4461
2 1186 62584 1
2 63744 85641 5313
1 20658 59024 63800 1
2 51424 82606 5804
2 90768 91321 1
3 15951 1 1
2 51955 91548 1298
3 37870 8860 39509
3 8317 1 1
3 308 1 1
1 1977...

output:

0
30650
0
0
0
0
0
52497
2540
51822
0
22469
45077
10570
146261
11438
80060
21311
114935
197491
113332
156089
207620
36833
104730
21761
58044
72459
72699
105703
297859
98381
351013
75662
42544
50509
161825
375089
22703
209315
121760
4317
496943
121741
116864
11213
87742
871
452690
54302
100601
39830
2...

result:

ok 33262 numbers

Test #16:

score: 16
Accepted
time: 31ms
memory: 7876kb

input:

99997 99999
2 53252 91242 1
1 57337 88934 37260 1
1 16834 34642 93492 1
2 81166 94101 6093
1 46770 56947 41803 1
2 70882 88729 2179
2 55489 59818 1
1 29212 60579 61103 1
3 37904 1447 28743
1 68609 95313 51191 1
1 41758 51157 38733 1
3 57276 44404 49850
1 53448 66120 27464 1
1 64716 86889 8186 1
1 30...

output:

27297
5447
87454
7764
0
36668
9059
202784
226798
35791
44217
20176
425699
841344
314555
628121
279373
862035
1237442
638303
225509
1013325
143603
280017
469785
168019
102756
1008786
266597
5507
31097
1524290
288879
523157
706592
434088
1052960
282317
254606
633715
493060
281268
273353
139218
259977
...

result:

ok 16863 numbers

Subtask #4:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 33ms
memory: 7928kb

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
113738
113738
105774
113738
336593
0
63627
327136
290548
0
220294
137888
78268
58519
108806
0
84171
110920
11181
0
262388
189704
340745
183158
60159
330620
266786
200713
120333
292978
189222
99905
68739
0
0
302890
170639
84927
203028
8521
150941
0
0
0
10004
102049
0
168532...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%