oj.uz

Submission #494684

# Submission time Handle Problem Language Result Execution time Memory
494684 2021-12-16T01:59:57 Z jiahng Progression (NOI20_progression) C++14
100 / 100
 2337 ms 90236 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 (r < N) root->set(r,r,qryA(r+1)-(s+(r-l)*c));
			if (l > 1) root->set(l-1,l-1,s-qryA(l-1));
			
			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 259 ms 88740 KB Output is correct
2 Correct 100 ms 3560 KB Output is correct
3 Correct 106 ms 3460 KB Output is correct
4 Correct 120 ms 3652 KB Output is correct
5 Correct 108 ms 3548 KB Output is correct
6 Correct 98 ms 3692 KB Output is correct
7 Correct 123 ms 3580 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 332 KB Output is correct
11 Correct 226 ms 88720 KB Output is correct
12 Correct 226 ms 88620 KB Output is correct
13 Correct 205 ms 88524 KB Output is correct
14 Correct 243 ms 89168 KB Output is correct
15 Correct 215 ms 88900 KB Output is correct
16 Correct 249 ms 88572 KB Output is correct
17 Correct 251 ms 88124 KB Output is correct
18 Correct 259 ms 88680 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 2 ms 600 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 4 ms 640 KB Output is correct
18 Correct 4 ms 628 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 87240 KB Output is correct
2 Correct 124 ms 3012 KB Output is correct
3 Correct 105 ms 3008 KB Output is correct
4 Correct 116 ms 2960 KB Output is correct
5 Correct 118 ms 3224 KB Output is correct
6 Correct 120 ms 3076 KB Output is correct
7 Correct 149 ms 3052 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 324 KB Output is correct
11 Correct 634 ms 85844 KB Output is correct
12 Correct 505 ms 87288 KB Output is correct
13 Correct 646 ms 85808 KB Output is correct
14 Correct 647 ms 85820 KB Output is correct
15 Correct 569 ms 87088 KB Output is correct
16 Correct 625 ms 87696 KB Output is correct
17 Correct 687 ms 87812 KB Output is correct
18 Correct 636 ms 87864 KB Output is correct
19 Correct 515 ms 87128 KB Output is correct
20 Correct 592 ms 87072 KB Output is correct
21 Correct 554 ms 87084 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1174 ms 89772 KB Output is correct
2 Correct 236 ms 3612 KB Output is correct
3 Correct 244 ms 3736 KB Output is correct
4 Correct 189 ms 3532 KB Output is correct
5 Correct 226 ms 3756 KB Output is correct
6 Correct 199 ms 3640 KB Output is correct
7 Correct 178 ms 3664 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1102 ms 86648 KB Output is correct
12 Correct 1099 ms 89992 KB Output is correct
13 Correct 1100 ms 86648 KB Output is correct
14 Correct 1156 ms 86724 KB Output is correct
15 Correct 1076 ms 89312 KB Output is correct
16 Correct 1234 ms 90188 KB Output is correct
17 Correct 1152 ms 89956 KB Output is correct
18 Correct 1216 ms 89896 KB Output is correct
19 Correct 1175 ms 89888 KB Output is correct
20 Correct 1178 ms 89880 KB Output is correct
21 Correct 1200 ms 89920 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 87240 KB Output is correct
2 Correct 124 ms 3012 KB Output is correct
3 Correct 105 ms 3008 KB Output is correct
4 Correct 116 ms 2960 KB Output is correct
5 Correct 118 ms 3224 KB Output is correct
6 Correct 120 ms 3076 KB Output is correct
7 Correct 149 ms 3052 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 324 KB Output is correct
11 Correct 634 ms 85844 KB Output is correct
12 Correct 505 ms 87288 KB Output is correct
13 Correct 646 ms 85808 KB Output is correct
14 Correct 647 ms 85820 KB Output is correct
15 Correct 569 ms 87088 KB Output is correct
16 Correct 625 ms 87696 KB Output is correct
17 Correct 687 ms 87812 KB Output is correct
18 Correct 636 ms 87864 KB Output is correct
19 Correct 515 ms 87128 KB Output is correct
20 Correct 592 ms 87072 KB Output is correct
21 Correct 554 ms 87084 KB Output is correct
22 Correct 1779 ms 89340 KB Output is correct
23 Correct 259 ms 3556 KB Output is correct
24 Correct 280 ms 3528 KB Output is correct
25 Correct 239 ms 3548 KB Output is correct
26 Correct 246 ms 3576 KB Output is correct
27 Correct 221 ms 3496 KB Output is correct
28 Correct 198 ms 3500 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 328 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1878 ms 86432 KB Output is correct
33 Correct 1582 ms 89404 KB Output is correct
34 Correct 1735 ms 86692 KB Output is correct
35 Correct 1742 ms 86648 KB Output is correct
36 Correct 1380 ms 86516 KB Output is correct
37 Correct 1339 ms 86416 KB Output is correct
38 Correct 1235 ms 86432 KB Output is correct
39 Correct 1655 ms 89408 KB Output is correct
40 Correct 1777 ms 89588 KB Output is correct
41 Correct 1568 ms 89524 KB Output is correct
42 Correct 1834 ms 89304 KB Output is correct
43 Correct 1589 ms 89404 KB Output is correct
44 Correct 1575 ms 89252 KB Output is correct
45 Correct 1536 ms 89524 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 88740 KB Output is correct
2 Correct 100 ms 3560 KB Output is correct
3 Correct 106 ms 3460 KB Output is correct
4 Correct 120 ms 3652 KB Output is correct
5 Correct 108 ms 3548 KB Output is correct
6 Correct 98 ms 3692 KB Output is correct
7 Correct 123 ms 3580 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 332 KB Output is correct
11 Correct 226 ms 88720 KB Output is correct
12 Correct 226 ms 88620 KB Output is correct
13 Correct 205 ms 88524 KB Output is correct
14 Correct 243 ms 89168 KB Output is correct
15 Correct 215 ms 88900 KB Output is correct
16 Correct 249 ms 88572 KB Output is correct
17 Correct 251 ms 88124 KB Output is correct
18 Correct 259 ms 88680 KB Output is correct
19 Correct 4 ms 588 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 2 ms 612 KB Output is correct
28 Correct 3 ms 724 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 3 ms 600 KB Output is correct
31 Correct 2 ms 600 KB Output is correct
32 Correct 3 ms 588 KB Output is correct
33 Correct 3 ms 592 KB Output is correct
34 Correct 4 ms 588 KB Output is correct
35 Correct 4 ms 640 KB Output is correct
36 Correct 4 ms 628 KB Output is correct
37 Correct 2 ms 384 KB Output is correct
38 Correct 2 ms 332 KB Output is correct
39 Correct 2 ms 332 KB Output is correct
40 Correct 600 ms 87240 KB Output is correct
41 Correct 124 ms 3012 KB Output is correct
42 Correct 105 ms 3008 KB Output is correct
43 Correct 116 ms 2960 KB Output is correct
44 Correct 118 ms 3224 KB Output is correct
45 Correct 120 ms 3076 KB Output is correct
46 Correct 149 ms 3052 KB Output is correct
47 Correct 1 ms 336 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Correct 1 ms 324 KB Output is correct
50 Correct 634 ms 85844 KB Output is correct
51 Correct 505 ms 87288 KB Output is correct
52 Correct 646 ms 85808 KB Output is correct
53 Correct 647 ms 85820 KB Output is correct
54 Correct 569 ms 87088 KB Output is correct
55 Correct 625 ms 87696 KB Output is correct
56 Correct 687 ms 87812 KB Output is correct
57 Correct 636 ms 87864 KB Output is correct
58 Correct 515 ms 87128 KB Output is correct
59 Correct 592 ms 87072 KB Output is correct
60 Correct 554 ms 87084 KB Output is correct
61 Correct 1174 ms 89772 KB Output is correct
62 Correct 236 ms 3612 KB Output is correct
63 Correct 244 ms 3736 KB Output is correct
64 Correct 189 ms 3532 KB Output is correct
65 Correct 226 ms 3756 KB Output is correct
66 Correct 199 ms 3640 KB Output is correct
67 Correct 178 ms 3664 KB Output is correct
68 Correct 1 ms 332 KB Output is correct
69 Correct 2 ms 320 KB Output is correct
70 Correct 1 ms 332 KB Output is correct
71 Correct 1102 ms 86648 KB Output is correct
72 Correct 1099 ms 89992 KB Output is correct
73 Correct 1100 ms 86648 KB Output is correct
74 Correct 1156 ms 86724 KB Output is correct
75 Correct 1076 ms 89312 KB Output is correct
76 Correct 1234 ms 90188 KB Output is correct
77 Correct 1152 ms 89956 KB Output is correct
78 Correct 1216 ms 89896 KB Output is correct
79 Correct 1175 ms 89888 KB Output is correct
80 Correct 1178 ms 89880 KB Output is correct
81 Correct 1200 ms 89920 KB Output is correct
82 Correct 1779 ms 89340 KB Output is correct
83 Correct 259 ms 3556 KB Output is correct
84 Correct 280 ms 3528 KB Output is correct
85 Correct 239 ms 3548 KB Output is correct
86 Correct 246 ms 3576 KB Output is correct
87 Correct 221 ms 3496 KB Output is correct
88 Correct 198 ms 3500 KB Output is correct
89 Correct 1 ms 332 KB Output is correct
90 Correct 1 ms 328 KB Output is correct
91 Correct 1 ms 332 KB Output is correct
92 Correct 1878 ms 86432 KB Output is correct
93 Correct 1582 ms 89404 KB Output is correct
94 Correct 1735 ms 86692 KB Output is correct
95 Correct 1742 ms 86648 KB Output is correct
96 Correct 1380 ms 86516 KB Output is correct
97 Correct 1339 ms 86416 KB Output is correct
98 Correct 1235 ms 86432 KB Output is correct
99 Correct 1655 ms 89408 KB Output is correct
100 Correct 1777 ms 89588 KB Output is correct
101 Correct 1568 ms 89524 KB Output is correct
102 Correct 1834 ms 89304 KB Output is correct
103 Correct 1589 ms 89404 KB Output is correct
104 Correct 1575 ms 89252 KB Output is correct
105 Correct 1536 ms 89524 KB Output is correct
106 Correct 2141 ms 90180 KB Output is correct
107 Correct 318 ms 3700 KB Output is correct
108 Correct 284 ms 3640 KB Output is correct
109 Correct 299 ms 3740 KB Output is correct
110 Correct 1 ms 372 KB Output is correct
111 Correct 1 ms 376 KB Output is correct
112 Correct 1 ms 380 KB Output is correct
113 Correct 1909 ms 89084 KB Output is correct
114 Correct 1521 ms 89388 KB Output is correct
115 Correct 1772 ms 89404 KB Output is correct
116 Correct 1586 ms 89332 KB Output is correct
117 Correct 1878 ms 90236 KB Output is correct
118 Correct 1506 ms 89276 KB Output is correct
119 Correct 1778 ms 89084 KB Output is correct
120 Correct 691 ms 87936 KB Output is correct
121 Correct 710 ms 87868 KB Output is correct
122 Correct 918 ms 87788 KB Output is correct
123 Correct 650 ms 87096 KB Output is correct
124 Correct 569 ms 86944 KB Output is correct
125 Correct 574 ms 87168 KB Output is correct
126 Correct 2174 ms 87088 KB Output is correct
127 Correct 2188 ms 86900 KB Output is correct
128 Correct 2050 ms 90068 KB Output is correct
129 Correct 1996 ms 86864 KB Output is correct
130 Correct 1462 ms 86920 KB Output is correct
131 Correct 1529 ms 86924 KB Output is correct
132 Correct 1553 ms 86900 KB Output is correct
133 Correct 2162 ms 89936 KB Output is correct
134 Correct 2337 ms 89804 KB Output is correct
135 Correct 2144 ms 89856 KB Output is correct
136 Correct 284 ms 3904 KB Output is correct
137 Correct 304 ms 3740 KB Output is correct
138 Correct 303 ms 3632 KB Output is correct