oj.uz

Submission #494671

# Submission time Handle Problem Language Result Execution time Memory
494671 2021-12-16T01:43:21 Z jiahng Progression (NOI20_progression) C++14
61 / 100
 3000 ms 90112 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, int _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,lazyadd=0,lazyset=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){
	return A[p];
	if (p == 1) return A[1];
	else return 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 3075 ms 80164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 81152 KB Output is correct
2 Correct 100 ms 900 KB Output is correct
3 Correct 101 ms 836 KB Output is correct
4 Correct 73 ms 904 KB Output is correct
5 Correct 93 ms 960 KB Output is correct
6 Correct 90 ms 880 KB Output is correct
7 Correct 124 ms 1128 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 495 ms 80928 KB Output is correct
12 Correct 447 ms 81240 KB Output is correct
13 Correct 507 ms 80916 KB Output is correct
14 Correct 480 ms 80836 KB Output is correct
15 Correct 438 ms 81108 KB Output is correct
16 Correct 460 ms 81516 KB Output is correct
17 Correct 506 ms 81416 KB Output is correct
18 Correct 513 ms 81504 KB Output is correct
19 Correct 442 ms 80792 KB Output is correct
20 Correct 411 ms 80840 KB Output is correct
21 Correct 451 ms 80832 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 80508 KB Output is correct
2 Correct 134 ms 400 KB Output is correct
3 Correct 152 ms 3640 KB Output is correct
4 Correct 159 ms 3588 KB Output is correct
5 Correct 161 ms 3620 KB Output is correct
6 Correct 171 ms 3648 KB Output is correct
7 Correct 165 ms 3912 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 916 ms 86656 KB Output is correct
12 Correct 842 ms 90020 KB Output is correct
13 Correct 884 ms 86656 KB Output is correct
14 Correct 865 ms 86744 KB Output is correct
15 Correct 758 ms 89904 KB Output is correct
16 Correct 887 ms 90076 KB Output is correct
17 Correct 875 ms 90100 KB Output is correct
18 Correct 876 ms 90112 KB Output is correct
19 Correct 808 ms 90072 KB Output is correct
20 Correct 851 ms 89996 KB Output is correct
21 Correct 800 ms 89948 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 81152 KB Output is correct
2 Correct 100 ms 900 KB Output is correct
3 Correct 101 ms 836 KB Output is correct
4 Correct 73 ms 904 KB Output is correct
5 Correct 93 ms 960 KB Output is correct
6 Correct 90 ms 880 KB Output is correct
7 Correct 124 ms 1128 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 495 ms 80928 KB Output is correct
12 Correct 447 ms 81240 KB Output is correct
13 Correct 507 ms 80916 KB Output is correct
14 Correct 480 ms 80836 KB Output is correct
15 Correct 438 ms 81108 KB Output is correct
16 Correct 460 ms 81516 KB Output is correct
17 Correct 506 ms 81416 KB Output is correct
18 Correct 513 ms 81504 KB Output is correct
19 Correct 442 ms 80792 KB Output is correct
20 Correct 411 ms 80840 KB Output is correct
21 Correct 451 ms 80832 KB Output is correct
22 Execution timed out 3085 ms 80260 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 3075 ms 80164 KB Time limit exceeded
2 Halted 0 ms 0 KB -