Submission #674672

#	Time	Username	Problem	Language	Result	Execution time	Memory
674672		QwertyPi	Progression (NOI20_progression)	C++14	100 / 100	1192 ms	103508 KiB

Progression

#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 type = 2, s = t.s, c = t.c;
		}
		
		tag shift(int n) {
			return {type, s + n * c, c};
		}
		
		void pr() {
			printf("tag(%d %d %d)\n", type, s, 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 (stderr)

Progression.cpp: In member function 'void SegTree::tag::pr()':
Progression.cpp:26:17: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   26 |    printf("tag(%d %d %d)\n", type, s, c);
      |                ~^            ~~~~
      |                 |            |
      |                 int          long long int
      |                %lld
Progression.cpp:26:20: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   26 |    printf("tag(%d %d %d)\n", type, s, c);
      |                   ~^               ~
      |                    |               |
      |                    int             long long int
      |                   %lld
Progression.cpp:26:23: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   26 |    printf("tag(%d %d %d)\n", type, s, c);
      |                      ~^               ~
      |                       |               |
      |                       int             long long int
      |                      %lld
Progression.cpp: In member function 'void SegTree::node::pr()':
Progression.cpp:81:13: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   81 |    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:81:19: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   81 |    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:81:22: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   81 |    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:81:25: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
   81 |    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:81:32: warning: format '%d' expects argument of type 'int', but argument 6 has type 'long long int' [-Wformat=]
   81 |    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:81:35: warning: format '%d' expects argument of type 'int', but argument 7 has type 'long long int' [-Wformat=]
   81 |    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:81:38: warning: format '%d' expects argument of type 'int', but argument 8 has type 'long long int' [-Wformat=]
   81 |    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:81:42: warning: format '%d' expects argument of type 'int', but argument 9 has type 'long long int' [-Wformat=]
   81 |    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 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17