oj.uz

Submission #405294

# Submission time Handle Problem Language Result Execution time Memory
405294 2021-05-16T07:29:47 Z oolimry Progression (NOI20_progression) C++17
35 / 100
 371 ms 125080 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

struct thing{
	lint leftval, rightval, leftcnt, rightcnt, best, full;
};

inline thing single(int u){
	return {u,u,1,1,1,1};
}

inline thing merge(thing L, thing R){
	thing res;
	if(L.full and R.full and L.rightval == R.leftval){
		return {L.leftval, R.rightval, L.leftcnt+R.leftcnt, L.rightcnt+R.rightcnt, L.best+R.best, 1};
	}
	
	res.leftval = L.leftval, res.rightval = R.rightval;
	res.leftcnt = L.leftcnt, res.rightcnt = R.rightcnt;
	res.best = max(L.best, R.best);
	res.full = 0;
	
	if(L.rightval == R.leftval){
		res.best = max(res.best, L.rightcnt + R.leftcnt);
		if(L.full) res.leftcnt += R.leftcnt;
		else if(R.full) res.rightcnt += L.rightcnt;
		res.best = max(res.best, res.leftcnt);
		res.best = max(res.best, res.rightcnt);
	}
	
	return res;
}

lint arr[300005];
struct node{
	int s, e, m;
	thing val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s == e) val = single(arr[s]);
		else{
			l = new node(s,m);
			r = new node(m+1,e);
			val = merge(l->val, r->val);
		}	
	}
	
	void push(){
		
	}
	
	thing query(int S, int E){
		push();
		if(s == S and E == e) return val;
		else if(E <= m) return l->query(S,E);
		else if(S >= m+1) return r->query(S,E);
		else return merge(l->query(S,m), r->query(m+1,E));
	} 
} *root;


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, Q; cin >> n >> Q;
	lint x; cin >> x;
	for(int i = 2;i <= n;i++){
		lint y; cin >> y;
		arr[i-1] = y-x;
		x = y;
	}
	
	if(n != 1) root = new node(1,n-1);
	
	while(Q--){
		int t, l, r; cin >> t >> l >> r;
		if(t == 3){
			if(l == r) cout << "1\n";
			else cout << root->query(l,r-1).best+1 << '\n';
		}
		else{
			if(n == 1) continue;
		}
	}
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 63304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 64104 KB Output is correct
2 Correct 108 ms 3012 KB Output is correct
3 Correct 94 ms 2972 KB Output is correct
4 Correct 86 ms 2892 KB Output is correct
5 Correct 98 ms 3060 KB Output is correct
6 Correct 100 ms 3096 KB Output is correct
7 Correct 97 ms 3140 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 361 ms 64796 KB Output is correct
12 Correct 310 ms 66068 KB Output is correct
13 Correct 366 ms 64720 KB Output is correct
14 Correct 364 ms 64628 KB Output is correct
15 Correct 317 ms 66040 KB Output is correct
16 Correct 363 ms 66676 KB Output is correct
17 Correct 371 ms 66628 KB Output is correct
18 Correct 363 ms 66800 KB Output is correct
19 Correct 309 ms 65924 KB Output is correct
20 Correct 311 ms 66120 KB Output is correct
21 Correct 311 ms 65960 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 199 ms 119492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 64104 KB Output is correct
2 Correct 108 ms 3012 KB Output is correct
3 Correct 94 ms 2972 KB Output is correct
4 Correct 86 ms 2892 KB Output is correct
5 Correct 98 ms 3060 KB Output is correct
6 Correct 100 ms 3096 KB Output is correct
7 Correct 97 ms 3140 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 361 ms 64796 KB Output is correct
12 Correct 310 ms 66068 KB Output is correct
13 Correct 366 ms 64720 KB Output is correct
14 Correct 364 ms 64628 KB Output is correct
15 Correct 317 ms 66040 KB Output is correct
16 Correct 363 ms 66676 KB Output is correct
17 Correct 371 ms 66628 KB Output is correct
18 Correct 363 ms 66800 KB Output is correct
19 Correct 309 ms 65924 KB Output is correct
20 Correct 311 ms 66120 KB Output is correct
21 Correct 311 ms 65960 KB Output is correct
22 Runtime error 223 ms 125080 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 63304 KB Output isn't correct
2 Halted 0 ms 0 KB -