oj.uz

답안 #405288

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405288 2021-05-16T07:25:06 Z oolimry Progression (NOI20_progression) C++17
0 / 100
 753 ms 1048580 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;
	}
	
	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';
		}
	}
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 65552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 66044 KB Output is correct
2 Correct 98 ms 3008 KB Output is correct
3 Correct 97 ms 2976 KB Output is correct
4 Correct 84 ms 2884 KB Output is correct
5 Correct 98 ms 3156 KB Output is correct
6 Correct 96 ms 3112 KB Output is correct
7 Correct 100 ms 3140 KB Output is correct
8 Runtime error 753 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 216 ms 124668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 66044 KB Output is correct
2 Correct 98 ms 3008 KB Output is correct
3 Correct 97 ms 2976 KB Output is correct
4 Correct 84 ms 2884 KB Output is correct
5 Correct 98 ms 3156 KB Output is correct
6 Correct 96 ms 3112 KB Output is correct
7 Correct 100 ms 3140 KB Output is correct
8 Runtime error 753 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 65552 KB Output isn't correct
2 Halted 0 ms 0 KB -