oj.uz

Submission #494679

# Submission time Handle Problem Language Result Execution time Memory
494679 2021-12-16T01:56:20 Z jiahng Progression (NOI20_progression) C++14
35 / 100
 3000 ms 164556 KB 
#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 (l > 1) root->set(l-1,l-1,s-qryA(l-1));
			if (r < N) root->set(r,r,qryA(r+1)-(s+(r-l)*c));
			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
0 / 9.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 972 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 87112 KB Output is correct
2 Correct 119 ms 2968 KB Output is correct
3 Correct 99 ms 3032 KB Output is correct
4 Correct 85 ms 2900 KB Output is correct
5 Correct 122 ms 3048 KB Output is correct
6 Correct 121 ms 3108 KB Output is correct
7 Correct 125 ms 3056 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 674 ms 85840 KB Output is correct
12 Correct 560 ms 87140 KB Output is correct
13 Correct 683 ms 85824 KB Output is correct
14 Correct 682 ms 85752 KB Output is correct
15 Correct 636 ms 87156 KB Output is correct
16 Correct 698 ms 87740 KB Output is correct
17 Correct 732 ms 87680 KB Output is correct
18 Correct 774 ms 87824 KB Output is correct
19 Correct 648 ms 87076 KB Output is correct
20 Correct 594 ms 87152 KB Output is correct
21 Correct 582 ms 87084 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 298 ms 164556 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 87112 KB Output is correct
2 Correct 119 ms 2968 KB Output is correct
3 Correct 99 ms 3032 KB Output is correct
4 Correct 85 ms 2900 KB Output is correct
5 Correct 122 ms 3048 KB Output is correct
6 Correct 121 ms 3108 KB Output is correct
7 Correct 125 ms 3056 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 674 ms 85840 KB Output is correct
12 Correct 560 ms 87140 KB Output is correct
13 Correct 683 ms 85824 KB Output is correct
14 Correct 682 ms 85752 KB Output is correct
15 Correct 636 ms 87156 KB Output is correct
16 Correct 698 ms 87740 KB Output is correct
17 Correct 732 ms 87680 KB Output is correct
18 Correct 774 ms 87824 KB Output is correct
19 Correct 648 ms 87076 KB Output is correct
20 Correct 594 ms 87152 KB Output is correct
21 Correct 582 ms 87084 KB Output is correct
22 Execution timed out 3031 ms 84548 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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