oj.uz

Submission #674670

# Submission time Handle Problem Language Result Execution time Memory
674670 2022-12-25T18:08:25 Z QwertyPi Progression (NOI20_progression) C++14
35 / 100
 3000 ms 176492 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){
		cout << "patch " << ql << ' ' << qr << ' ' << s << ' ' << c << ' ' << v << ' ' << l << ' ' << r << endl;
		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
0 / 9.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 852 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 935 ms 93916 KB Output is correct
2 Correct 516 ms 1908 KB Output is correct
3 Correct 559 ms 1868 KB Output is correct
4 Correct 533 ms 2068 KB Output is correct
5 Correct 525 ms 1904 KB Output is correct
6 Correct 534 ms 1956 KB Output is correct
7 Correct 532 ms 1940 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 2 ms 308 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 989 ms 94664 KB Output is correct
12 Correct 915 ms 95044 KB Output is correct
13 Correct 969 ms 94780 KB Output is correct
14 Correct 979 ms 94648 KB Output is correct
15 Correct 905 ms 95056 KB Output is correct
16 Correct 1035 ms 95368 KB Output is correct
17 Correct 990 ms 95308 KB Output is correct
18 Correct 977 ms 95532 KB Output is correct
19 Correct 929 ms 94652 KB Output is correct
20 Correct 928 ms 94640 KB Output is correct
21 Correct 921 ms 94624 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 169256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 93916 KB Output is correct
2 Correct 516 ms 1908 KB Output is correct
3 Correct 559 ms 1868 KB Output is correct
4 Correct 533 ms 2068 KB Output is correct
5 Correct 525 ms 1904 KB Output is correct
6 Correct 534 ms 1956 KB Output is correct
7 Correct 532 ms 1940 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 2 ms 308 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 989 ms 94664 KB Output is correct
12 Correct 915 ms 95044 KB Output is correct
13 Correct 969 ms 94780 KB Output is correct
14 Correct 979 ms 94648 KB Output is correct
15 Correct 905 ms 95056 KB Output is correct
16 Correct 1035 ms 95368 KB Output is correct
17 Correct 990 ms 95308 KB Output is correct
18 Correct 977 ms 95532 KB Output is correct
19 Correct 929 ms 94652 KB Output is correct
20 Correct 928 ms 94640 KB Output is correct
21 Correct 921 ms 94624 KB Output is correct
22 Execution timed out 3072 ms 176492 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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