oj.uz

Submission #676491

# Submission time Handle Problem Language Result Execution time Memory
676491 2022-12-31T03:38:28 Z penguin133 Progression (NOI20_progression) C++17
100 / 100
 1270 ms 88264 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second

int A[300005];


struct pain{
	int val, pmax, smax, pref, suf, len, sm;
};

pain merge(pain l, pain r){
	pain ans;
	ans.val = max(l.val, r.val);
	ans.len = l.len + r.len;
	if(l.suf == r.pref)ans.val = max(ans.val, l.smax + r.pmax);
	ans.suf = r.suf, ans.pref = l.pref;
	ans.pmax = l.pmax, ans.smax = r.smax;
	if(l.suf == r.suf && r.smax == r.len)ans.smax += l.smax;
	if(l.pref == r.pref && l.pmax == l.len)ans.pmax += r.pmax;
	ans.sm = l.sm + r.sm;
	return ans;
}

struct node{
	int s,e,m;
	pain hi;
	bool fix;
	int lazy, lazy2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		lazy = 0;
		fix = 0;
		lazy2 = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
			hi = merge(l->hi, r->hi);
		}
		else{
			hi.val = hi.pmax = hi.smax = 1;
			hi.pref = hi.sm = hi.suf = A[s] - A[s-1];
			hi.len = 1;
		}
	}
	void propo(){
		if(fix){
			hi.pmax = hi.smax = hi.val = hi.len, hi.pref = hi.suf = lazy2;
			hi.sm = lazy2 * (e - s + 1);
			fix = 0;
			if(s != e)l->lazy2 = lazy2, r->lazy2 = lazy2, l->fix = 1, r->fix = 1, l->lazy = 0, r->lazy = 0;
		}
		else if(lazy){
			hi.pref += lazy;
			hi.suf += lazy;
			hi.sm += lazy * (e - s + 1);
			if(s != e){
				if(l->fix)l->lazy = 0, l->lazy2 += lazy;
				else l->lazy += lazy;
				if(r->fix)r->lazy = 0, r->lazy2 += lazy;
				else r->lazy += lazy;
			}
		}
		lazy = lazy2 = 0;
	}
	void upd(int a, int b, int c){
		propo();
		if(a == s && b == e){
			if(fix)lazy2 += c;
			else lazy += c;
			propo();
		}
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->propo(), r->propo();
			hi = merge(l->hi, r->hi);
		}
	}
	void upd2(int a, int b, int c){
		propo();
		if(a == s && b == e)lazy2 =c, fix = 1, lazy = 0, propo();
		else{
			if(b <= m)l->upd2(a, b, c);
			else if(a > m)r->upd2(a, b, c);
			else l->upd2(a, m, c), r->upd2(m+1, b, c);
			l->propo(), r->propo();
			hi = merge(l->hi ,r->hi);
		}
	}
	pain query(int a, int b){
		propo();
		if(a == s && b == e)return hi;
		else if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return merge(l->query(a, m), r->query(m+1, b));
	}
	void debug(){
		cerr << s << " " << e << " " << hi.val << " " << hi.pref << " " << hi.suf << " " << hi.pmax << " " << hi.smax << " " << hi.len << " " << hi.sm << '\n';
		if(s != e)l->debug(), r->debug();
	}
}*root;


int n,q;
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q;
	for(int i=1;i<=n;i++)cin >> A[i];
	root = new node(1, n);
	//root->debug();
	while(q--){
		int x,l,r;cin >> x >> l >> r;
		if(x == 3)cout << (l == r ? 1 : root->query(l+1, r).val + 1) << '\n';
		else if(x == 1){
			int s,c;cin >>s >> c;
			root->upd(l, l, s);
			if(l < r)root->upd(l+1, r, c);
			if(r < n)root->upd(r+1, r+1, -(s + (r-l)*c));
		}
		else{
			int s, c;cin >> s >> c;
			int tmp = 0;
			if(r < n)tmp = root->query(1, r+1).sm;
			if(l > 1){
				//pain test = root->query(1, l-1);
				//cout << test.val << " " << test.pref << " " << test.suf << " " << test.pmax << " " << test.smax << " " << test.len << " " << test.sm << '\n';
				int x = root->query(1, l-1).sm;
				root->upd2(l, l, s-x);
				//cout << s << " " << x << '\n';
			}
			else{
				root->upd2(1, 1, s);
			}
			if(l < r)root->upd2(l+1, r, c);
			if(r < n){
				int x = root->query(1, r).sm;
				root->upd2(r+1, r+1, tmp-(s + (r-l)*c));
			}
		}
	}
}

Compilation message

Progression.cpp: In function 'int32_t main()':
Progression.cpp:144:9: warning: unused variable 'x' [-Wunused-variable]
  144 |     int x = root->query(1, r).sm;
      |         ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 86320 KB Output is correct
2 Correct 137 ms 3456 KB Output is correct
3 Correct 140 ms 3544 KB Output is correct
4 Correct 129 ms 3544 KB Output is correct
5 Correct 124 ms 3512 KB Output is correct
6 Correct 164 ms 3616 KB Output is correct
7 Correct 118 ms 3532 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 334 ms 86392 KB Output is correct
12 Correct 319 ms 86292 KB Output is correct
13 Correct 357 ms 86528 KB Output is correct
14 Correct 437 ms 86744 KB Output is correct
15 Correct 318 ms 86556 KB Output is correct
16 Correct 332 ms 86332 KB Output is correct
17 Correct 321 ms 86332 KB Output is correct
18 Correct 307 ms 86336 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 5 ms 608 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 3 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 84848 KB Output is correct
2 Correct 82 ms 2992 KB Output is correct
3 Correct 74 ms 2956 KB Output is correct
4 Correct 66 ms 2928 KB Output is correct
5 Correct 88 ms 3152 KB Output is correct
6 Correct 92 ms 3216 KB Output is correct
7 Correct 91 ms 3088 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 379 ms 83416 KB Output is correct
12 Correct 324 ms 84808 KB Output is correct
13 Correct 402 ms 83468 KB Output is correct
14 Correct 407 ms 83476 KB Output is correct
15 Correct 345 ms 84836 KB Output is correct
16 Correct 379 ms 85380 KB Output is correct
17 Correct 395 ms 85432 KB Output is correct
18 Correct 397 ms 85392 KB Output is correct
19 Correct 341 ms 84832 KB Output is correct
20 Correct 368 ms 84812 KB Output is correct
21 Correct 355 ms 84800 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 87576 KB Output is correct
2 Correct 125 ms 3584 KB Output is correct
3 Correct 128 ms 3664 KB Output is correct
4 Correct 119 ms 3564 KB Output is correct
5 Correct 123 ms 3688 KB Output is correct
6 Correct 132 ms 3676 KB Output is correct
7 Correct 153 ms 3652 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 730 ms 84436 KB Output is correct
12 Correct 651 ms 87744 KB Output is correct
13 Correct 698 ms 84388 KB Output is correct
14 Correct 662 ms 84372 KB Output is correct
15 Correct 625 ms 87504 KB Output is correct
16 Correct 705 ms 87820 KB Output is correct
17 Correct 687 ms 87612 KB Output is correct
18 Correct 691 ms 87700 KB Output is correct
19 Correct 663 ms 87632 KB Output is correct
20 Correct 683 ms 87624 KB Output is correct
21 Correct 704 ms 87636 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 84848 KB Output is correct
2 Correct 82 ms 2992 KB Output is correct
3 Correct 74 ms 2956 KB Output is correct
4 Correct 66 ms 2928 KB Output is correct
5 Correct 88 ms 3152 KB Output is correct
6 Correct 92 ms 3216 KB Output is correct
7 Correct 91 ms 3088 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 379 ms 83416 KB Output is correct
12 Correct 324 ms 84808 KB Output is correct
13 Correct 402 ms 83468 KB Output is correct
14 Correct 407 ms 83476 KB Output is correct
15 Correct 345 ms 84836 KB Output is correct
16 Correct 379 ms 85380 KB Output is correct
17 Correct 395 ms 85432 KB Output is correct
18 Correct 397 ms 85392 KB Output is correct
19 Correct 341 ms 84832 KB Output is correct
20 Correct 368 ms 84812 KB Output is correct
21 Correct 355 ms 84800 KB Output is correct
22 Correct 923 ms 87096 KB Output is correct
23 Correct 116 ms 3500 KB Output is correct
24 Correct 114 ms 3548 KB Output is correct
25 Correct 114 ms 3516 KB Output is correct
26 Correct 120 ms 3520 KB Output is correct
27 Correct 118 ms 3556 KB Output is correct
28 Correct 120 ms 3528 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 900 ms 84304 KB Output is correct
33 Correct 962 ms 86980 KB Output is correct
34 Correct 902 ms 84284 KB Output is correct
35 Correct 904 ms 84268 KB Output is correct
36 Correct 727 ms 84080 KB Output is correct
37 Correct 739 ms 84172 KB Output is correct
38 Correct 720 ms 84256 KB Output is correct
39 Correct 883 ms 87100 KB Output is correct
40 Correct 927 ms 87268 KB Output is correct
41 Correct 905 ms 87520 KB Output is correct
42 Correct 931 ms 87104 KB Output is correct
43 Correct 847 ms 87064 KB Output is correct
44 Correct 874 ms 87332 KB Output is correct
45 Correct 917 ms 87164 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 86320 KB Output is correct
2 Correct 137 ms 3456 KB Output is correct
3 Correct 140 ms 3544 KB Output is correct
4 Correct 129 ms 3544 KB Output is correct
5 Correct 124 ms 3512 KB Output is correct
6 Correct 164 ms 3616 KB Output is correct
7 Correct 118 ms 3532 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 334 ms 86392 KB Output is correct
12 Correct 319 ms 86292 KB Output is correct
13 Correct 357 ms 86528 KB Output is correct
14 Correct 437 ms 86744 KB Output is correct
15 Correct 318 ms 86556 KB Output is correct
16 Correct 332 ms 86332 KB Output is correct
17 Correct 321 ms 86332 KB Output is correct
18 Correct 307 ms 86336 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 2 ms 596 KB Output is correct
34 Correct 5 ms 608 KB Output is correct
35 Correct 2 ms 596 KB Output is correct
36 Correct 2 ms 596 KB Output is correct
37 Correct 1 ms 336 KB Output is correct
38 Correct 3 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 342 ms 84848 KB Output is correct
41 Correct 82 ms 2992 KB Output is correct
42 Correct 74 ms 2956 KB Output is correct
43 Correct 66 ms 2928 KB Output is correct
44 Correct 88 ms 3152 KB Output is correct
45 Correct 92 ms 3216 KB Output is correct
46 Correct 91 ms 3088 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 1 ms 332 KB Output is correct
50 Correct 379 ms 83416 KB Output is correct
51 Correct 324 ms 84808 KB Output is correct
52 Correct 402 ms 83468 KB Output is correct
53 Correct 407 ms 83476 KB Output is correct
54 Correct 345 ms 84836 KB Output is correct
55 Correct 379 ms 85380 KB Output is correct
56 Correct 395 ms 85432 KB Output is correct
57 Correct 397 ms 85392 KB Output is correct
58 Correct 341 ms 84832 KB Output is correct
59 Correct 368 ms 84812 KB Output is correct
60 Correct 355 ms 84800 KB Output is correct
61 Correct 673 ms 87576 KB Output is correct
62 Correct 125 ms 3584 KB Output is correct
63 Correct 128 ms 3664 KB Output is correct
64 Correct 119 ms 3564 KB Output is correct
65 Correct 123 ms 3688 KB Output is correct
66 Correct 132 ms 3676 KB Output is correct
67 Correct 153 ms 3652 KB Output is correct
68 Correct 1 ms 340 KB Output is correct
69 Correct 1 ms 340 KB Output is correct
70 Correct 1 ms 340 KB Output is correct
71 Correct 730 ms 84436 KB Output is correct
72 Correct 651 ms 87744 KB Output is correct
73 Correct 698 ms 84388 KB Output is correct
74 Correct 662 ms 84372 KB Output is correct
75 Correct 625 ms 87504 KB Output is correct
76 Correct 705 ms 87820 KB Output is correct
77 Correct 687 ms 87612 KB Output is correct
78 Correct 691 ms 87700 KB Output is correct
79 Correct 663 ms 87632 KB Output is correct
80 Correct 683 ms 87624 KB Output is correct
81 Correct 704 ms 87636 KB Output is correct
82 Correct 923 ms 87096 KB Output is correct
83 Correct 116 ms 3500 KB Output is correct
84 Correct 114 ms 3548 KB Output is correct
85 Correct 114 ms 3516 KB Output is correct
86 Correct 120 ms 3520 KB Output is correct
87 Correct 118 ms 3556 KB Output is correct
88 Correct 120 ms 3528 KB Output is correct
89 Correct 1 ms 340 KB Output is correct
90 Correct 1 ms 340 KB Output is correct
91 Correct 1 ms 336 KB Output is correct
92 Correct 900 ms 84304 KB Output is correct
93 Correct 962 ms 86980 KB Output is correct
94 Correct 902 ms 84284 KB Output is correct
95 Correct 904 ms 84268 KB Output is correct
96 Correct 727 ms 84080 KB Output is correct
97 Correct 739 ms 84172 KB Output is correct
98 Correct 720 ms 84256 KB Output is correct
99 Correct 883 ms 87100 KB Output is correct
100 Correct 927 ms 87268 KB Output is correct
101 Correct 905 ms 87520 KB Output is correct
102 Correct 931 ms 87104 KB Output is correct
103 Correct 847 ms 87064 KB Output is correct
104 Correct 874 ms 87332 KB Output is correct
105 Correct 917 ms 87164 KB Output is correct
106 Correct 1218 ms 88152 KB Output is correct
107 Correct 161 ms 3696 KB Output is correct
108 Correct 160 ms 3664 KB Output is correct
109 Correct 160 ms 3808 KB Output is correct
110 Correct 1 ms 340 KB Output is correct
111 Correct 1 ms 340 KB Output is correct
112 Correct 1 ms 340 KB Output is correct
113 Correct 932 ms 87168 KB Output is correct
114 Correct 1012 ms 87188 KB Output is correct
115 Correct 912 ms 87112 KB Output is correct
116 Correct 853 ms 87164 KB Output is correct
117 Correct 1165 ms 88060 KB Output is correct
118 Correct 861 ms 87044 KB Output is correct
119 Correct 965 ms 87064 KB Output is correct
120 Correct 382 ms 85640 KB Output is correct
121 Correct 381 ms 85452 KB Output is correct
122 Correct 384 ms 85540 KB Output is correct
123 Correct 325 ms 84812 KB Output is correct
124 Correct 328 ms 84812 KB Output is correct
125 Correct 326 ms 84812 KB Output is correct
126 Correct 1154 ms 84716 KB Output is correct
127 Correct 1246 ms 84728 KB Output is correct
128 Correct 1181 ms 88224 KB Output is correct
129 Correct 1270 ms 84676 KB Output is correct
130 Correct 833 ms 84740 KB Output is correct
131 Correct 828 ms 84884 KB Output is correct
132 Correct 909 ms 84896 KB Output is correct
133 Correct 1183 ms 88264 KB Output is correct
134 Correct 1211 ms 88192 KB Output is correct
135 Correct 1190 ms 88232 KB Output is correct
136 Correct 163 ms 3656 KB Output is correct
137 Correct 163 ms 3660 KB Output is correct
138 Correct 160 ms 3688 KB Output is correct