oj.uz

Submission #674671

# Submission time Handle Problem Language Result Execution time Memory
674671 2022-12-25T18:09:07 Z QwertyPi Progression (NOI20_progression) C++14
68 / 100
 1185 ms 102460 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 3e5 + 11;

int d[MAXN];

struct SegTree{
	
	struct tag{
		tag() = default;
		tag(int _type, int _s, int _c) : type(_type), s(_s), c(_c) {};
		int type, s, c;
		
		void operator+= (const tag& t) {
			if(t.type == 1) s += t.s, c += t.c;
			else s = t.s, c = t.c;
		}
		
		tag shift(int n) {
			return {type, s + n * c, c};
		}
	} lazy[MAXN << 2];
	
	struct node{
		int ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size;
		node() = default;
		node(int idx, int val) {
			if(idx == -1) { ans = -1; return; }
			ans = 1; _size = 1; pf_s = sf_s = val; pf_c = sf_c = 0; pf_x = sf_x = 1;
		}
		friend node operator+ (const node& a, const node& b) {
			if(a.ans == -1 || b.ans == -1) return a.ans == -1 ? b : a;
			node res; res.ans = max(a.ans, b.ans); res._size = a._size + b._size;
			
			res.pf_s = a.pf_s, res.pf_c = a.pf_c, res.pf_x = a.pf_x;
			if(a.pf_x == a._size){
				if(a._size == 1){
					res.pf_c = b.pf_s - a.sf_s;
					res.pf_x = res.pf_c == b.pf_c ? 1 + b.pf_x : 2;
				}else if(a.sf_s + a.sf_c == b.pf_s){
					res.pf_x = a.pf_x + (a.pf_c == b.pf_c ? b.pf_x : 1); 
				}
			}
			
			res.sf_s = b.sf_s, res.sf_c = b.sf_c, res.sf_x = b.sf_x;
			if(b.sf_x == b._size){
				if(b._size == 1){
					res.sf_c = b.pf_s - a.sf_s;
					res.sf_x = res.sf_c == a.sf_c ? 1 + a.sf_x : 2;
				}else if(a.sf_s + b.pf_c == b.pf_s){
					res.sf_x = b.sf_x + (b.sf_c == a.sf_c ? a.sf_x : 1); 
				}
			}

			res.ans = max(res.ans, max(res.pf_x, res.sf_x));
			res.ans = max(res.ans, 2LL);
			if(a.sf_s + b.pf_c == b.pf_s){
				res.ans = max(res.ans, 1 + b.pf_x);
			}
			if(a.sf_s + a.sf_c == b.pf_s){
				res.ans = max(res.ans, 1 + a.sf_x);
			}
			if(a.sf_s + a.sf_c == b.pf_s && a.sf_c == b.pf_c){
				res.ans = max(res.ans, a.sf_x + b.pf_x);
			}
			return res;
		}
		
		void operator+= (const tag& t) {
			if(t.type == 1) pf_s += t.s, pf_c += t.c, sf_s += t.s + t.c * (_size - 1), sf_c += t.c;
			else ans = pf_x = sf_x = _size, pf_s = t.s, pf_c = t.c, sf_s = t.s + t.c * (_size - 1), sf_c = t.c;
		}
		
		void pr() {
			printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
		}
	} t[MAXN << 2];
	
	void push(int v){
		t[v * 2 + 1] += lazy[v];
		lazy[v * 2 + 1] += lazy[v];
		t[v * 2 + 2] += lazy[v].shift(t[v * 2 + 1]._size);
		lazy[v * 2 + 2] += lazy[v].shift(t[v * 2 + 1]._size);
		lazy[v] = tag(1, 0, 0);
	}
	
	void build(int v, int l, int r){
		lazy[v] = tag(1, 0, 0);
		if(l == r) {
			t[v] = node(l, d[l]);
			return;
		}
		int m = (l + r) / 2;
		build(v * 2 + 1, l, m);
		build(v * 2 + 2, m + 1, r);
		t[v] = t[v * 2 + 1] + t[v * 2 + 2];
	}
	
	void patch(int ql, int qr, int s, int c, int v, int l, int r){
		if(qr < l || r < ql) return;
		if(ql <= l && r <= qr) {
			tag _t(1, s + c * (l - ql), c);
			lazy[v] += _t;
			t[v] += _t;
			return;
		}
		push(v);
		int m = (l + r) / 2;
		patch(ql, qr, s, c, v * 2 + 1, l, m);
		patch(ql, qr, s, c, v * 2 + 2, m + 1, r);
		t[v] = t[v * 2 + 1] + t[v * 2 + 2];
	}
	
	void rewrite(int ql, int qr, int s, int c, int v, int l, int r){
		if(qr < l || r < ql) return;
		if(ql <= l && r <= qr) {
			tag _t(2, s + c * (l - ql), c);
			lazy[v] += _t;
			t[v] += _t;
			return;
		}
		push(v);
		int m = (l + r) / 2;
		rewrite(ql, qr, s, c, v * 2 + 1, l, m);
		rewrite(ql, qr, s, c, v * 2 + 2, m + 1, r);
		t[v] = t[v * 2 + 1] + t[v * 2 + 2];
	}
	
	node eval(int ql, int qr, int v, int l, int r){
		if(qr < l || r < ql) return node(-1, 0);
		if(ql <= l && r <= qr) return t[v];
		push(v);
		int m = (l + r) / 2;
		node a = eval(ql, qr, v * 2 + 1, l, m);
		node b = eval(ql, qr, v * 2 + 2, m + 1, r);
		return a + b;
	}
} segTree;

int32_t main(){
	int n, q; cin >> n >> q;
	for(int i = 0; i < n; i++) cin >> d[i];
	segTree.build(0, 0, n - 1);
	for(int i = 0; i < q; i++){
		int ty, l, r, s, c; cin >> ty >> l >> r; l--; r--;
		if(ty == 1){
			cin >> s >> c;
			segTree.patch(l, r, s, c, 0, 0, n - 1);
		}else if(ty == 2){
			cin >> s >> c;
			segTree.rewrite(l, r, s, c, 0, 0, n - 1);
		}else{
			SegTree::node _node = segTree.eval(l, r, 0, 0, n - 1);
			cout << _node.ans << endl;
		}
	}
}

Compilation message

Progression.cpp: In member function 'void SegTree::node::pr()':
Progression.cpp:77:13: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   77 |    printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
      |            ~^                                  ~~~
      |             |                                  |
      |             int                                long long int
      |            %lld
Progression.cpp:77:19: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   77 |    printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
      |                  ~^                                 ~~~~
      |                   |                                 |
      |                   int                               long long int
      |                  %lld
Progression.cpp:77:22: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   77 |    printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
      |                     ~^                                    ~~~~
      |                      |                                    |
      |                      int                                  long long int
      |                     %lld
Progression.cpp:77:25: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
   77 |    printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
      |                        ~^                                       ~~~~
      |                         |                                       |
      |                         int                                     long long int
      |                        %lld
Progression.cpp:77:32: warning: format '%d' expects argument of type 'int', but argument 6 has type 'long long int' [-Wformat=]
   77 |    printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
      |                               ~^                                      ~~~~
      |                                |                                      |
      |                                int                                    long long int
      |                               %lld
Progression.cpp:77:35: warning: format '%d' expects argument of type 'int', but argument 7 has type 'long long int' [-Wformat=]
   77 |    printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
      |                                  ~^                                         ~~~~
      |                                   |                                         |
      |                                   int                                       long long int
      |                                  %lld
Progression.cpp:77:38: warning: format '%d' expects argument of type 'int', but argument 8 has type 'long long int' [-Wformat=]
   77 |    printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
      |                                     ~^                                            ~~~~
      |                                      |                                            |
      |                                      int                                          long long int
      |                                     %lld
Progression.cpp:77:42: warning: format '%d' expects argument of type 'int', but argument 9 has type 'long long int' [-Wformat=]
   77 |    printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
      |                                         ~^                                              ~~~~~
      |                                          |                                              |
      |                                          int                                            long long int
      |                                         %lld

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 93624 KB Output is correct
2 Correct 334 ms 1808 KB Output is correct
3 Correct 318 ms 1692 KB Output is correct
4 Correct 324 ms 1800 KB Output is correct
5 Correct 321 ms 1840 KB Output is correct
6 Correct 329 ms 1720 KB Output is correct
7 Correct 325 ms 1736 KB Output is correct
8 Correct 2 ms 320 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 529 ms 94648 KB Output is correct
12 Correct 546 ms 94600 KB Output is correct
13 Correct 536 ms 95056 KB Output is correct
14 Correct 655 ms 94952 KB Output is correct
15 Correct 538 ms 94960 KB Output is correct
16 Correct 548 ms 94612 KB Output is correct
17 Correct 532 ms 94656 KB Output is correct
18 Correct 533 ms 94680 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 892 ms 94040 KB Output is correct
2 Correct 518 ms 896 KB Output is correct
3 Correct 510 ms 868 KB Output is correct
4 Correct 510 ms 848 KB Output is correct
5 Correct 517 ms 948 KB Output is correct
6 Correct 516 ms 1000 KB Output is correct
7 Correct 521 ms 856 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 904 ms 93748 KB Output is correct
12 Correct 886 ms 94044 KB Output is correct
13 Correct 927 ms 93716 KB Output is correct
14 Correct 911 ms 93688 KB Output is correct
15 Correct 879 ms 93936 KB Output is correct
16 Correct 943 ms 94240 KB Output is correct
17 Correct 955 ms 94360 KB Output is correct
18 Correct 950 ms 94508 KB Output is correct
19 Correct 899 ms 93748 KB Output is correct
20 Correct 911 ms 93604 KB Output is correct
21 Correct 961 ms 93652 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 93384 KB Output is correct
2 Correct 356 ms 1628 KB Output is correct
3 Correct 356 ms 1788 KB Output is correct
4 Correct 348 ms 1640 KB Output is correct
5 Correct 358 ms 1788 KB Output is correct
6 Correct 351 ms 1588 KB Output is correct
7 Correct 361 ms 1752 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 872 ms 94176 KB Output is correct
12 Correct 927 ms 94324 KB Output is correct
13 Correct 858 ms 94284 KB Output is correct
14 Correct 868 ms 94028 KB Output is correct
15 Correct 895 ms 94044 KB Output is correct
16 Correct 964 ms 94012 KB Output is correct
17 Correct 959 ms 94016 KB Output is correct
18 Correct 956 ms 93996 KB Output is correct
19 Correct 925 ms 93700 KB Output is correct
20 Correct 934 ms 93600 KB Output is correct
21 Correct 945 ms 93404 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 892 ms 94040 KB Output is correct
2 Correct 518 ms 896 KB Output is correct
3 Correct 510 ms 868 KB Output is correct
4 Correct 510 ms 848 KB Output is correct
5 Correct 517 ms 948 KB Output is correct
6 Correct 516 ms 1000 KB Output is correct
7 Correct 521 ms 856 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 904 ms 93748 KB Output is correct
12 Correct 886 ms 94044 KB Output is correct
13 Correct 927 ms 93716 KB Output is correct
14 Correct 911 ms 93688 KB Output is correct
15 Correct 879 ms 93936 KB Output is correct
16 Correct 943 ms 94240 KB Output is correct
17 Correct 955 ms 94360 KB Output is correct
18 Correct 950 ms 94508 KB Output is correct
19 Correct 899 ms 93748 KB Output is correct
20 Correct 911 ms 93604 KB Output is correct
21 Correct 961 ms 93652 KB Output is correct
22 Correct 1150 ms 93344 KB Output is correct
23 Correct 406 ms 3548 KB Output is correct
24 Correct 400 ms 3760 KB Output is correct
25 Correct 401 ms 3520 KB Output is correct
26 Correct 401 ms 3508 KB Output is correct
27 Correct 400 ms 3652 KB Output is correct
28 Correct 405 ms 3496 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 212 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 1105 ms 99596 KB Output is correct
33 Correct 1105 ms 102412 KB Output is correct
34 Correct 1058 ms 99492 KB Output is correct
35 Correct 1082 ms 99376 KB Output is correct
36 Correct 1059 ms 99236 KB Output is correct
37 Correct 1109 ms 99276 KB Output is correct
38 Correct 1083 ms 99568 KB Output is correct
39 Correct 1127 ms 102132 KB Output is correct
40 Correct 1185 ms 102460 KB Output is correct
41 Correct 1139 ms 102432 KB Output is correct
42 Correct 1162 ms 102244 KB Output is correct
43 Correct 1095 ms 102348 KB Output is correct
44 Correct 1106 ms 102352 KB Output is correct
45 Correct 1108 ms 102252 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 93624 KB Output is correct
2 Correct 334 ms 1808 KB Output is correct
3 Correct 318 ms 1692 KB Output is correct
4 Correct 324 ms 1800 KB Output is correct
5 Correct 321 ms 1840 KB Output is correct
6 Correct 329 ms 1720 KB Output is correct
7 Correct 325 ms 1736 KB Output is correct
8 Correct 2 ms 320 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 529 ms 94648 KB Output is correct
12 Correct 546 ms 94600 KB Output is correct
13 Correct 536 ms 95056 KB Output is correct
14 Correct 655 ms 94952 KB Output is correct
15 Correct 538 ms 94960 KB Output is correct
16 Correct 548 ms 94612 KB Output is correct
17 Correct 532 ms 94656 KB Output is correct
18 Correct 533 ms 94680 KB Output is correct
19 Incorrect 3 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -