Submission #494684

#	Time	Username	Problem	Language	Result	Execution time	Memory
494684		jiahng	Progression (NOI20_progression)	C++14	100 / 100	2337 ms	90236 KiB

Progression

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(int i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define MOD 1000000007
#define maxn 300010
#define data data1


struct data{
	int llen, rlen, lval, rval, sz, val, sm;
	data(int _sz, int _val, int _llen, int _rlen, int _lval, int _rval, __int128 _sm){
		llen = _llen; val = _val; rlen = _rlen, lval = _lval, rval = _rval; sz = _sz;
		sm = _sm;
	}
};

data merge(data x, data y){
	 int lval = x.lval, rval = y.rval;
	 int llen, rlen;
	 if (x.llen == x.sz && x.rval == y.lval) llen = x.llen + y.llen;
	 else llen = x.llen;
	 
	 if (y.rlen == y.sz && y.lval == x.rval) rlen = y.rlen + x.rlen;
	 else rlen = y.rlen;
	 
	 int val = max(x.val, y.val);
	 if (x.rval == y.lval) val = max(val, x.rlen + y.llen);
	 
	 return data(x.sz + y.sz, val, llen, rlen, lval, rval, x.sm + y.sm);
}
int N,Q;
int A[maxn],B[maxn];
struct node{
	int s,e,m,lazyset=0,lazyadd=0;
	bool lazyset_flag = 0;
	data dat = data(0,0,0,0,0,0,0);
	node *l,*r;
	node (int ss,int ee){
		s = ss; e = ee; m = (s + e) / 2;
		if (s == e){
			dat = data(1, 1, 1, 1, B[s], B[s],B[s]);
		}else{
			l = new node(s,m); r = new node(m+1,e);
			dat = merge(l->dat, r->dat);
		}
	}

	void prop(){
		if (lazyadd != 0){
			dat.lval += lazyadd; dat.rval += lazyadd; dat.sm += lazyadd * (e-s+1);
		}
		if (lazyset_flag){
			dat = data(e-s+1,e-s+1,e-s+1,e-s+1,lazyset,lazyset,(e-s+1)*lazyset);
		}
		
		
		if (s != e){
			if (lazyset_flag){
				l->lazyset_flag = r->lazyset_flag = 1;
				l->lazyadd = r->lazyadd = 0;
				l->lazyset = r->lazyset = lazyset;
			}
			if (lazyadd != 0){
				if (l->lazyset_flag) l->lazyset += lazyadd;
				else l->lazyadd += lazyadd;
				
				if (r->lazyset_flag) r->lazyset += lazyadd;
				else r->lazyadd += lazyadd;
			}
		}
				
		lazyadd = 0; lazyset_flag = 0; lazyset = 0;
	}
	void set(int a,int b,int c){
		prop();
		if (a <= s && e <= b){
			lazyset_flag = 1; lazyset = c; lazyadd = 0;
			prop();
		}else if (a > e || s > b) return;
		else{
			l->set(a,b,c); r->set(a,b,c);
			l->prop(); r->prop();
			dat = merge(l->dat, r->dat);
		}
	}
	void add(int a,int b,int c){
		prop();
		if (a <= s && e <= b){
			if (lazyset_flag) lazyset += c;
			else lazyadd += c;
			prop();
		}else if (a > e || s > b) return;
		else{
			l->add(a,b,c); r->add(a,b,c);
			l->prop(); r->prop();
			dat = merge(l->dat, r->dat);
		}
	}
	
	int qry(int a,int b){ // Largest contiguous equal sequence
		if (a > b) return 0;
		if (a == b) return 1;
		prop();
		if (a <= s && e <= b) return dat.val;
		else if (a > e || s > b) return 0;
		else{
			l->prop(); r->prop();
			int res = max(l->qry(a,b), r->qry(a,b));
			l->prop(); r->prop();
			if (l->dat.rval == r->dat.lval){
				int x = l->e - l->dat.rlen + 1;
				int y = r->s + r->dat.llen - 1;
				x = max(x, a); y = min(y, b);
				res = max(res, y - x + 1);;
			}
			return res;
		}
	}
	int sum(int a,int b){
		prop();
		if (a <= s && e <= b) return dat.sm;
		else if (a > e || s > b) return 0;
		else return l->sum(a,b)+ r->sum(a,b);
	}
}*root;

int qryA(int p){
	//~ int x = 0;
	//~ FOR(i,1,p-1){
		//~ cout << (ll)root->sum(i,i) << ' ' << A[i+1] - A[i] << ' ' << i << '\n';
		//~ assert((ll)root->sum(i,i) == A[i+1] - A[i]);
		//~ x += (ll)root->sum(i,i);
	//~ }
	//~ return x + A[1];
	if (p == 1) return A[1];
	else return ll(A[1] + root->sum(1, p-1));
}

int32_t main(){
    fast;
    cin >> N >> Q;
    FOR(i,1,N) cin >> A[i];
    FOR(i,1,N-1) B[i] = A[i+1] - A[i];
    if (N > 1) root = new node(1,N-1);

    int t,l,r,s,c;
    FOR(q,1,Q){
		cin >> t;
		if (t == 1){ // add
			cin >> l >> r >> s >> c;
			if (N == 1) continue;
			
			if (l > 1){
				root->add(l-1,l-1,s);
				//~ cout << "ADD " << l-1 << ' ' << l-1 << ' ' << s << '\n';
			}
			if (r < N){
				root->add(r,r,-(s+(r-l)*c));
				//~ cout << "ADD " << r << ' ' << r << ' ' << -(s+(r-l)*c) << '\n';
			}
			if (l < r) root->add(l,r-1,c);
			//~ cout << "ADD " << l << ' ' << r-1 << ' ' << c << '\n';
			//~ FOR(i,l,r) A[i] += s + (i-l)*c;
			if (l == 1) A[1] += s;
		}else if (t == 2){ //set
			cin >> l >> r >> s >> c;
			if (N == 1) continue;
			//~ FOR(i,l,r) A[i] = s + (i-l)*c;
			if (r < N) root->set(r,r,qryA(r+1)-(s+(r-l)*c));
			if (l > 1) root->set(l-1,l-1,s-qryA(l-1));
			
			if (l < r) root->set(l,r-1,c);
			if (l == 1) A[1] = s;
		}else{
			cin >> l >> r;
			if (N == 1 || l == r) cout << 1 << '\n';
			else cout << root->qry(l,r-1) + 1 << '\n';
		}
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17