oj.uz

Submission #494668

# Submission time Handle Problem Language Result Execution time Memory
494668 2021-12-16T01:39:11 Z jiahng Progression (NOI20_progression) C++14
57 / 100
 1828 ms 87612 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 80752 KB Output is correct
2 Correct 84 ms 552 KB Output is correct
3 Correct 88 ms 524 KB Output is correct
4 Correct 88 ms 556 KB Output is correct
5 Correct 86 ms 648 KB Output is correct
6 Correct 80 ms 652 KB Output is correct
7 Correct 79 ms 540 KB Output is correct
8 Correct 1 ms 216 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 167 ms 80692 KB Output is correct
12 Correct 224 ms 80684 KB Output is correct
13 Correct 201 ms 81148 KB Output is correct
14 Correct 168 ms 80988 KB Output is correct
15 Correct 172 ms 80964 KB Output is correct
16 Correct 189 ms 80780 KB Output is correct
17 Correct 181 ms 80704 KB Output is correct
18 Correct 181 ms 80660 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Incorrect 2 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 81148 KB Output is correct
2 Correct 93 ms 824 KB Output is correct
3 Correct 86 ms 888 KB Output is correct
4 Correct 110 ms 800 KB Output is correct
5 Correct 103 ms 976 KB Output is correct
6 Correct 88 ms 904 KB Output is correct
7 Correct 94 ms 956 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 518 ms 80940 KB Output is correct
12 Correct 600 ms 81116 KB Output is correct
13 Correct 564 ms 81004 KB Output is correct
14 Correct 521 ms 80832 KB Output is correct
15 Correct 452 ms 81044 KB Output is correct
16 Correct 530 ms 81548 KB Output is correct
17 Correct 481 ms 81488 KB Output is correct
18 Correct 512 ms 81604 KB Output is correct
19 Correct 464 ms 80840 KB Output is correct
20 Correct 419 ms 80840 KB Output is correct
21 Correct 433 ms 80812 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 80436 KB Output is correct
2 Incorrect 146 ms 500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 81148 KB Output is correct
2 Correct 93 ms 824 KB Output is correct
3 Correct 86 ms 888 KB Output is correct
4 Correct 110 ms 800 KB Output is correct
5 Correct 103 ms 976 KB Output is correct
6 Correct 88 ms 904 KB Output is correct
7 Correct 94 ms 956 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 518 ms 80940 KB Output is correct
12 Correct 600 ms 81116 KB Output is correct
13 Correct 564 ms 81004 KB Output is correct
14 Correct 521 ms 80832 KB Output is correct
15 Correct 452 ms 81044 KB Output is correct
16 Correct 530 ms 81548 KB Output is correct
17 Correct 481 ms 81488 KB Output is correct
18 Correct 512 ms 81604 KB Output is correct
19 Correct 464 ms 80840 KB Output is correct
20 Correct 419 ms 80840 KB Output is correct
21 Correct 433 ms 80812 KB Output is correct
22 Correct 1529 ms 80456 KB Output is correct
23 Correct 179 ms 612 KB Output is correct
24 Correct 158 ms 608 KB Output is correct
25 Correct 168 ms 632 KB Output is correct
26 Correct 173 ms 548 KB Output is correct
27 Correct 189 ms 576 KB Output is correct
28 Correct 214 ms 560 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1585 ms 80564 KB Output is correct
33 Correct 1466 ms 80524 KB Output is correct
34 Correct 1449 ms 80860 KB Output is correct
35 Correct 1553 ms 80512 KB Output is correct
36 Correct 1114 ms 80728 KB Output is correct
37 Correct 1153 ms 80772 KB Output is correct
38 Correct 1210 ms 80744 KB Output is correct
39 Correct 1532 ms 84476 KB Output is correct
40 Correct 1828 ms 80788 KB Output is correct
41 Correct 1631 ms 80576 KB Output is correct
42 Correct 1620 ms 80512 KB Output is correct
43 Correct 1388 ms 87532 KB Output is correct
44 Correct 1461 ms 87612 KB Output is correct
45 Correct 1694 ms 86356 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 80752 KB Output is correct
2 Correct 84 ms 552 KB Output is correct
3 Correct 88 ms 524 KB Output is correct
4 Correct 88 ms 556 KB Output is correct
5 Correct 86 ms 648 KB Output is correct
6 Correct 80 ms 652 KB Output is correct
7 Correct 79 ms 540 KB Output is correct
8 Correct 1 ms 216 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 167 ms 80692 KB Output is correct
12 Correct 224 ms 80684 KB Output is correct
13 Correct 201 ms 81148 KB Output is correct
14 Correct 168 ms 80988 KB Output is correct
15 Correct 172 ms 80964 KB Output is correct
16 Correct 189 ms 80780 KB Output is correct
17 Correct 181 ms 80704 KB Output is correct
18 Correct 181 ms 80660 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Incorrect 2 ms 332 KB Output isn't correct
21 Halted 0 ms 0 KB -