oj.uz

Submission #674669

# Submission time Handle Problem Language Result Execution time Memory
674669 2022-12-25T17:53:18 Z QwertyPi Progression (NOI20_progression) C++14
55 / 100
 1174 ms 103108 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);
			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);
			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 529 ms 93572 KB Output is correct
2 Correct 330 ms 3544 KB Output is correct
3 Correct 330 ms 3504 KB Output is correct
4 Correct 323 ms 3536 KB Output is correct
5 Correct 344 ms 3540 KB Output is correct
6 Correct 317 ms 3712 KB Output is correct
7 Correct 325 ms 3564 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 530 ms 101472 KB Output is correct
12 Correct 571 ms 101416 KB Output is correct
13 Correct 542 ms 101860 KB Output is correct
14 Correct 575 ms 101792 KB Output is correct
15 Correct 528 ms 101620 KB Output is correct
16 Correct 532 ms 101464 KB Output is correct
17 Correct 541 ms 101564 KB Output is correct
18 Correct 531 ms 101364 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 885 ms 93888 KB Output is correct
2 Correct 518 ms 2924 KB Output is correct
3 Correct 511 ms 2912 KB Output is correct
4 Correct 506 ms 3040 KB Output is correct
5 Correct 516 ms 3068 KB Output is correct
6 Correct 519 ms 3248 KB Output is correct
7 Correct 516 ms 3408 KB Output is correct
8 Correct 2 ms 316 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 312 KB Output is correct
11 Correct 930 ms 98728 KB Output is correct
12 Correct 890 ms 100000 KB Output is correct
13 Correct 916 ms 98696 KB Output is correct
14 Correct 908 ms 98656 KB Output is correct
15 Correct 868 ms 100124 KB Output is correct
16 Correct 955 ms 100516 KB Output is correct
17 Correct 940 ms 100612 KB Output is correct
18 Correct 973 ms 100584 KB Output is correct
19 Correct 908 ms 99916 KB Output is correct
20 Correct 895 ms 99880 KB Output is correct
21 Correct 905 ms 99876 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 972 ms 93252 KB Output is correct
2 Correct 347 ms 3648 KB Output is correct
3 Correct 360 ms 3724 KB Output is correct
4 Correct 348 ms 3548 KB Output is correct
5 Correct 367 ms 3640 KB Output is correct
6 Correct 354 ms 3660 KB Output is correct
7 Correct 353 ms 3552 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 929 ms 99520 KB Output is correct
12 Correct 939 ms 102832 KB Output is correct
13 Correct 857 ms 99476 KB Output is correct
14 Correct 868 ms 99668 KB Output is correct
15 Correct 915 ms 102752 KB Output is correct
16 Correct 983 ms 102960 KB Output is correct
17 Correct 1146 ms 103108 KB Output is correct
18 Correct 972 ms 103080 KB Output is correct
19 Correct 944 ms 102852 KB Output is correct
20 Correct 954 ms 102832 KB Output is correct
21 Correct 946 ms 102728 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 93888 KB Output is correct
2 Correct 518 ms 2924 KB Output is correct
3 Correct 511 ms 2912 KB Output is correct
4 Correct 506 ms 3040 KB Output is correct
5 Correct 516 ms 3068 KB Output is correct
6 Correct 519 ms 3248 KB Output is correct
7 Correct 516 ms 3408 KB Output is correct
8 Correct 2 ms 316 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 312 KB Output is correct
11 Correct 930 ms 98728 KB Output is correct
12 Correct 890 ms 100000 KB Output is correct
13 Correct 916 ms 98696 KB Output is correct
14 Correct 908 ms 98656 KB Output is correct
15 Correct 868 ms 100124 KB Output is correct
16 Correct 955 ms 100516 KB Output is correct
17 Correct 940 ms 100612 KB Output is correct
18 Correct 973 ms 100584 KB Output is correct
19 Correct 908 ms 99916 KB Output is correct
20 Correct 895 ms 99880 KB Output is correct
21 Correct 905 ms 99876 KB Output is correct
22 Incorrect 1174 ms 102092 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 93572 KB Output is correct
2 Correct 330 ms 3544 KB Output is correct
3 Correct 330 ms 3504 KB Output is correct
4 Correct 323 ms 3536 KB Output is correct
5 Correct 344 ms 3540 KB Output is correct
6 Correct 317 ms 3712 KB Output is correct
7 Correct 325 ms 3564 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 530 ms 101472 KB Output is correct
12 Correct 571 ms 101416 KB Output is correct
13 Correct 542 ms 101860 KB Output is correct
14 Correct 575 ms 101792 KB Output is correct
15 Correct 528 ms 101620 KB Output is correct
16 Correct 532 ms 101464 KB Output is correct
17 Correct 541 ms 101564 KB Output is correct
18 Correct 531 ms 101364 KB Output is correct
19 Incorrect 3 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -