oj.uz

Submission #494676

# Submission time Handle Problem Language Result Execution time Memory
494676 2021-12-16T01:48:51 Z jiahng Progression (NOI20_progression) C++14
50 / 100
 3000 ms 100436 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;
	__int128 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;
	__int128 lazyadd;
	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 += (__int128)lazyadd * (e-s+1);
		}
		if (lazyset_flag){
			dat = data(e-s+1,e-s+1,e-s+1,e-s+1,lazyset,lazyset,(__int128)(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;
		}
	}
	__int128 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) x += A[i+1] - A[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 3103 ms 98908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 3 ms 588 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 99920 KB Output is correct
2 Correct 95 ms 932 KB Output is correct
3 Correct 84 ms 900 KB Output is correct
4 Correct 68 ms 836 KB Output is correct
5 Correct 103 ms 1092 KB Output is correct
6 Correct 88 ms 964 KB Output is correct
7 Correct 90 ms 896 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 546 ms 99760 KB Output is correct
12 Correct 469 ms 99908 KB Output is correct
13 Correct 539 ms 99676 KB Output is correct
14 Correct 558 ms 99636 KB Output is correct
15 Correct 435 ms 100008 KB Output is correct
16 Correct 507 ms 100292 KB Output is correct
17 Correct 516 ms 100436 KB Output is correct
18 Correct 529 ms 100400 KB Output is correct
19 Correct 429 ms 99544 KB Output is correct
20 Correct 448 ms 99716 KB Output is correct
21 Correct 422 ms 99560 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 99920 KB Output is correct
2 Correct 95 ms 932 KB Output is correct
3 Correct 84 ms 900 KB Output is correct
4 Correct 68 ms 836 KB Output is correct
5 Correct 103 ms 1092 KB Output is correct
6 Correct 88 ms 964 KB Output is correct
7 Correct 90 ms 896 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 546 ms 99760 KB Output is correct
12 Correct 469 ms 99908 KB Output is correct
13 Correct 539 ms 99676 KB Output is correct
14 Correct 558 ms 99636 KB Output is correct
15 Correct 435 ms 100008 KB Output is correct
16 Correct 507 ms 100292 KB Output is correct
17 Correct 516 ms 100436 KB Output is correct
18 Correct 529 ms 100400 KB Output is correct
19 Correct 429 ms 99544 KB Output is correct
20 Correct 448 ms 99716 KB Output is correct
21 Correct 422 ms 99560 KB Output is correct
22 Execution timed out 3083 ms 99292 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 3103 ms 98908 KB Time limit exceeded
2 Halted 0 ms 0 KB -