Submission #939784

#	Time	Username	Problem	Language	Result	Execution time	Memory
939784		Litusiano	Progression (NOI20_progression)	C++17	0 / 100	414 ms	98084 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int INF = 1e15;
struct Node{
	pair<int,int> mxl = {-INF,INF}; // tot, val
	pair<int,int> mxr = {-INF,INF}; // tot, val
	pair<int,int> tot = {-INF,INF}; // tot, val
	int sz = 1;
	int sum = 0;
};	

struct SegTree{
	int n;
	vector<Node> seg; //mxl, 	
	vector<pair<bool,int>> lazy; // 0 add, 1 set

	Node merge(Node idx, Node idx1){
		Node ans;
		ans.sz = idx.sz + idx1.sz;
		ans.sum = idx.sum + idx1.sum;
		if(idx.mxl.first == -INF && idx1.mxl.first == -INF) return ans; // both are null nodes
		if(idx1.mxl.first == -INF) return idx; // just second is a null node
		if(idx.mxl.first == -INF) return idx1;
		ans.mxl = idx.mxl;
		pair<int,int> templeft = idx.mxl; //idx ALWAYS IN THE LEFT 
		if(idx.mxl.first == idx.sz){
			if(idx1.mxl.second == idx.mxl.second) templeft = {idx.sz + idx1.mxl.first, idx1.mxl.second};// join both lefts
			else templeft = idx.mxl;
		}
		ans.mxl = max(ans.mxl, templeft); // take max
		// repeat for right
		ans.mxr = idx.mxr;
		pair<int,int> tempright = idx.mxr; 
		if(idx1.mxr.first == idx1.sz){
			if(idx1.mxr.second == idx.mxr.second) tempright = {idx1.sz + idx.mxr.first, idx.mxr.second};// join both lefts
			else tempright = idx.mxr;
		}
		ans.mxr = max(ans.mxr, tempright); // take max

		// TAKE TOTAL
		ans.tot = max(ans.mxl, ans.mxr); 
		// JOIN THE MIDDLE, idx right and idx1 left
		pair<int,int> temptot = ans.tot;
		if(idx.mxr.second == idx1.mxl.second){
			temptot = {idx.mxr.first + idx1.mxl.first, idx.mxr.second};
		}
		ans.tot = max(ans.tot, temptot);
		return ans;
	}

	void build(vector<int> v){
		int n1 = v.size();
		n = 1;
		while(n < n1){
			n*=2; 
		}
		Node tmpn;
		seg.assign(2*n, tmpn); lazy.assign(2*n, {0,0});
		for(int i = 0; i<n1; i++){
			//cerr<<v[i]<<" ";
			seg[i+n].mxl = seg[i+n].mxr = seg[i+n].tot = {1,v[i]};
			seg[i+n].sz = 1;
			seg[i+n].sum = v[i];
		}
		for(int i = n-1; i>=1; i--) seg[i] = merge(seg[2*i], seg[2*i+1]);
	}
	void add(int idx, int v, int l, int r){
		seg[idx].sum += v * (r-l+1);
		lazy[idx].second += v;
		seg[idx].mxl.second += v;
		seg[idx].mxr.second += v;
		seg[idx].tot.second += v;
	}
	void set(int idx, int v, int l, int r){
		seg[idx].sum = (r-l+1) * v;
		lazy[idx].first = 1;
		lazy[idx].second = v;
		seg[idx].mxl.second = v;
		seg[idx].mxl.first = (r-l+1)/2;
		seg[idx].mxr.second = v;
		seg[idx].mxr.first = (r-l+1)/2;
		seg[idx].tot.second = v;
		seg[idx].tot.first = (r-l+1)/2;
	}
	void PushDown(int k, int l, int r){
		if(lazy[k].first == 0){
			//add
			if(lazy[2*k].first == 1) lazy[2*k] = {0,0};
			add(2*k, lazy[k].second, l,r);
			if(lazy[2*k+1].first == 1) lazy[2*k+1] = {0,0};
			add(2*k+1,lazy[k].second, l, r);
		}
		else{
			//set
			set(2*k, lazy[k].second, l, r);
		}
		lazy[k] = {0,0};
	}
	Node query(int ql, int qr, int k, int l, int r){
		if(ql <= l && r <= qr) return seg[k];
		if(l > qr || r < ql){
			Node tmp;
			return tmp;
		}
		PushDown(k,l,r);
		int m = (l+r)/2;
		Node x = query(ql,qr,2*k,l,m);
		Node y = query(ql,qr,2*k+1,m+1,r);
		return merge(x,y);
	}
	int query(int ql, int qr){
		Node x = query(ql,qr,1,0,n-1);
		// cout<<"X "<<ql<<" "<<qr<<" "<<x.tot.first<<" "<<x.tot.second<<endl;
		return x.tot.first;
	}
	void update(int ql, int qr, int tp, int v, int k, int l, int r){
		if(ql <= l && r <= qr){
			if(tp == 0){
				// add
				add(k,v,l,r);
				if(lazy[k].first == 1) lazy[k] = {0,0};
				lazy[k].second += v;
				return;
			}
			else{
				set(k,v,l,r);
				return;
			}
			PushDown(k,l,r);
			int m = (l+r)/2;
			update(ql,qr,tp,v, 2*k,l,m);
			update(ql,qr,tp,v, 2*k+1, m+1,r);
			seg[k] = merge(seg[2*k], seg[2*k+1]);
		}
	}
	void update(int ql, int qr, int tp, int v){
		if(ql > qr) return;
		update(ql,qr,tp,v,1, 0,n-1);
	}
	int sum(int ql, int qr){
		return query(ql,qr,1,0,n-1).sum;
	}
};

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,q; cin>>n>>q;
	vector<int> v(n); for(int& i : v) cin>>i;
	vector<int> dif;
	for(int i = 1; i<n; i++) dif.push_back(v[i-1] - v[i]);
	SegTree seg; seg.build(dif);
	int val = v[0];
	while(q--){
		int tp; cin>>tp;
		if(tp == 1){
			//add
			int l,r; cin>>l>>r; l--; r--;
			int s,c; cin>>s>>c;
			if(l == 0) v[0] += s;
			seg.update(l,r-1,0,c);
			seg.update(r,r,0,s);
			if(l) seg.update(l-1,l-1,0,-s);
		}
		else if(tp == 2){
			int l,r; cin>>l>>r; int s,c; cin>>s>>c;
			// seg.update(l,r-1,1,c); // set differences
			int sum = v[0];
			
			if(l) sum+=seg.sum(0,l-1);
			int val = s + (r-l)*s;
			int sum1 = v[0];
			if(r) sum1+=seg.sum(0,r-1);
			if(l == 0) v[0] = s;
			if(l) seg.update(l-1, l-1, 0, s-sum);
			seg.update(r,r,0, val-sum1);
			seg.update(l,r-1,1,c);
		}
		else{
			int l,r; cin>>l>>r; l--; r--;
			if(l == r){
				cout<<1<<endl; continue;
			}
			// cerr<<endl<<l<<" "<<r-1<<endl;
			cout<<seg.query(l,r-1)+1<<endl;
		}
	}
}

Compilation message (stderr)

Progression.cpp: In function 'int main()':
Progression.cpp:155:6: warning: unused variable 'val' [-Wunused-variable]
  155 |  int val = v[0];
      |      ^~~

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