oj.uz

답안 #829518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829518 2023-08-18T11:53:01 Z amunduzbaev 식물 비교 (IOI20_plants) C++17
30 / 100
 3127 ms 208812 KB 
#include "plants.h"

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
//~ #define int ll

const int inf = 1e9;
const int N = 2e5 + 5;

struct ST{
	ar<ll, 2> tree[N << 2];
	ll f[N << 2];
	
	void build(int lx, int rx, int x){
		if(lx == rx) { tree[x][1] = lx; return; };
		int m = (lx + rx) >> 1;
		build(lx, m, x << 1), build(m + 1, rx, x << 1 | 1);
		tree[x][1] = lx;
	}
	
	ST(){
		build(0, N, 1);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x << 1][0] += f[x];
		tree[x << 1 | 1][0] += f[x];
		f[x << 1] += f[x], f[x << 1 | 1] += f[x];
		f[x] = 0;
	}
	
	void add(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x][0] += v;
			f[x] += v;
			return;
		}
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x << 1), add(l, r, v, m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
	}
	
	void add(int l, int r, int v) { return add(l, r, v, 0, N, 1); }
	
	ar<ll, 2> get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return {inf, inf};
		if(lx >= l && rx <= r) return tree[x];
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		return min(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	ar<ll, 2> get(int l, int r){
		return get(l, r, 0, N, 1);
	}
}tree, R, builder, buildel;

vector<int> a;
vector<vector<int>> l_, r_;
int n;

void init(int k, vector<int> r) {
	
	n = r.size();
	a.resize(n);
	
	l_.resize(n, vector<int>(20, -1));
	r_.resize(n, vector<int>(20, -1));
	
	{
		int cnt = 0;
		for(int i=0;i<k - 1;i++) cnt += (r[i] == 0);
		for(int i=k - 1;;){
			tree.add(i, i, r[i] + cnt);
			buildel.add(i, i, 1);
			builder.add(i, i, 1);
			
			if(r[i]){
				R.add(i, i, r[i]);
			} else {
				R.add(i, i, inf);
			}
			
			cnt -= (r[(i + n - k + 1) % n] == 0);
			cnt += (r[i] == 0);
			i = (i + 1) % n;
			if(i == k - 1) break;
		}
	}
	
	auto to_r = [&](int p){
		int l = p, r = p + k - 1;
		ar<ll, 2> pp = buildel.get(l, min(r, n - 1));
		if(!pp[0] || r < n) return pp;
		return buildel.get(0, r - n);
	};
	auto to_l = [&](int p){
		int l = p - k + 1, r = p;
		ar<ll, 2> pp = builder.get(max(l, 0), r);
		if(!pp[0] || 0 <= l) return pp;
		return builder.get(n + l, n - 1);
	};
	
	for(int j=n;j>0;j--){
		//~ for(int i=0;i<n;i++) cout<<tree.get(i, i)[0]<<" ";
		//~ cout<<"\n";
		
		auto [v, p] = tree.get(0, n - 1);
		
		{
			ar<ll, 2> pp = to_r(p);
			while(pp[0] == 0){
				l_[pp[1]][0] = p;
				buildel.add(pp[1], pp[1], 1);
				pp = to_r(p);
			}
			pp = to_l(p);
			while(pp[0] == 0){
				r_[pp[1]][0] = p;
				builder.add(pp[1], pp[1], 1);
				pp = to_l(p);
			}
		}
		
		assert(v == 0);
		buildel.add(p, p, -1);
		builder.add(p, p, -1);
		
		a[p] = j;
		
		R.add(p, p, inf);
		tree.add(p, p, inf);
		{
			int l = p - k + 1, r = p;
			tree.add(max(l, 0), r, -1);
			R.add(max(l, 0), r, -1);
			if(l < 0) tree.add(n + l, n - 1, -1);
			if(l < 0) R.add(n + l, n - 1, -1);
			
			ar<ll, 2> pp = R.get(0, n - 1);
			while(pp[0] == 0){
				R.add(pp[1], pp[1], inf);
				{
					int l = pp[1] + 1, r = pp[1] + k - 1;
					tree.add(l, min(r, n - 1), 1);
					if(n <= r) tree.add(0,  r - n, 1);
				}
				pp = R.get(0, n - 1);
			}
		}
		{
			int l = p, r = p + k - 1;
			tree.add(l, min(r, n - 1), -1);
			if(n <= r) tree.add(0,  r - n, -1);
		}
	}
	
	for(int i=0;i<n;i++){
		if(~l_[i][0]) l_[i][0] = (i - l_[i][0] + n) % n;
		else l_[i][0] = 0;
		
		if(~r_[i][0]) r_[i][0] = (r_[i][0] - i + n) % n;
		else r_[i][0] = 0;
	}
	
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			l_[i][j] = l_[i][j - 1] + l_[(i - l_[i][j - 1] % n + n) % n][j - 1];
			r_[i][j] = r_[i][j - 1] + r_[(i + r_[i][j - 1]) % n][j - 1];
			//~ if(~l_[i][j - 1]) l_[i][j] = l_[l_[i][j - 1]][j - 1];
			//~ if(~r_[i][j - 1]) r_[i][j] = r_[r_[i][j - 1]][j - 1];
		}
	}
	
	//~ for(int i=0;i<n;i++) cout<<a[i]<<" ";
	//~ cout<<"\n";
	//~ for(int j=0;j<4;j++){
		//~ for(int i=0;i<n;i++){
			//~ cout<<l_[i][j]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<n;i++){
			//~ cout<<r_[i][j]<<" ";
		//~ } cout<<"\n";
		//~ cout<<"\n";
	//~ }
	
	return;
}

bool check(int x, int y){
	{
		int cur = x, dis = (x - y + n) % n;
		for(int j=19;~j;j--){
			if(dis > l_[cur][j]){
				dis -= l_[cur][j];
				cur = (cur - l_[cur][j] % n + n) % n;
			}
			//~ if(y < x){
				//~ if(l_[cur][j] <= x && y < l_[cur][j]) cur = l_[cur][j];
			//~ } else {
				//~ if(l_[cur][j] <= x || y < l_[cur][j]) cur = l_[cur][j];
			//~ }
		}
		
		if(l_[cur][0] && a[(y + dis) % n] > a[y]) return true;
	}
	
	{
		int cur = x, dis = (y - x + n) % n;
		for(int j=19;~j;j--){
			if(dis > r_[cur][j]){
				dis -= r_[cur][j];
				cur = (cur + r_[cur][j]) % n;
			}
			//~ if(y < x){
				//~ if(l_[cur][j] <= x && y < l_[cur][j]) cur = l_[cur][j];
			//~ } else {
				//~ if(l_[cur][j] <= x || y < l_[cur][j]) cur = l_[cur][j];
			//~ }
		}
		
		if(r_[cur][0] && a[(y - dis + n) % n] > a[y]) return true;
	}
	
	return false;
}

int compare_plants(int x, int y) {
	if(check(x, y)) return 1;
	if(check(y, x)) return -1;
	
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 33364 KB Output is correct
2 Correct 14 ms 33360 KB Output is correct
3 Correct 14 ms 33364 KB Output is correct
4 Correct 14 ms 33340 KB Output is correct
5 Correct 14 ms 33308 KB Output is correct
6 Correct 146 ms 36104 KB Output is correct
7 Correct 253 ms 42648 KB Output is correct
8 Correct 1145 ms 101284 KB Output is correct
9 Correct 1202 ms 101280 KB Output is correct
10 Correct 1166 ms 101316 KB Output is correct
11 Correct 1366 ms 101276 KB Output is correct
12 Correct 1218 ms 101276 KB Output is correct
13 Correct 1172 ms 101276 KB Output is correct
14 Correct 1795 ms 101280 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 33364 KB Output is correct
2 Correct 17 ms 33364 KB Output is correct
3 Correct 15 ms 33364 KB Output is correct
4 Correct 14 ms 33364 KB Output is correct
5 Correct 15 ms 33364 KB Output is correct
6 Correct 22 ms 33780 KB Output is correct
7 Correct 111 ms 39612 KB Output is correct
8 Correct 16 ms 33384 KB Output is correct
9 Correct 22 ms 33760 KB Output is correct
10 Correct 121 ms 39684 KB Output is correct
11 Correct 133 ms 39592 KB Output is correct
12 Correct 206 ms 39752 KB Output is correct
13 Correct 107 ms 39732 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 33364 KB Output is correct
2 Correct 17 ms 33364 KB Output is correct
3 Correct 15 ms 33364 KB Output is correct
4 Correct 14 ms 33364 KB Output is correct
5 Correct 15 ms 33364 KB Output is correct
6 Correct 22 ms 33780 KB Output is correct
7 Correct 111 ms 39612 KB Output is correct
8 Correct 16 ms 33384 KB Output is correct
9 Correct 22 ms 33760 KB Output is correct
10 Correct 121 ms 39684 KB Output is correct
11 Correct 133 ms 39592 KB Output is correct
12 Correct 206 ms 39752 KB Output is correct
13 Correct 107 ms 39732 KB Output is correct
14 Correct 233 ms 44940 KB Output is correct
15 Runtime error 3127 ms 208812 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 33364 KB Output is correct
2 Correct 14 ms 33324 KB Output is correct
3 Correct 125 ms 36796 KB Output is correct
4 Correct 1550 ms 104184 KB Output is correct
5 Correct 1708 ms 104268 KB Output is correct
6 Correct 2228 ms 104564 KB Output is correct
7 Correct 2461 ms 104764 KB Output is correct
8 Runtime error 2374 ms 208764 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 33364 KB Output is correct
2 Correct 15 ms 33328 KB Output is correct
3 Correct 14 ms 33264 KB Output is correct
4 Correct 13 ms 33364 KB Output is correct
5 Correct 14 ms 33348 KB Output is correct
6 Correct 21 ms 33364 KB Output is correct
7 Correct 53 ms 33956 KB Output is correct
8 Correct 27 ms 34004 KB Output is correct
9 Correct 39 ms 34316 KB Output is correct
10 Correct 31 ms 34392 KB Output is correct
11 Correct 48 ms 34304 KB Output is correct
12 Correct 44 ms 34404 KB Output is correct
13 Correct 28 ms 34328 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 33352 KB Output is correct
2 Correct 14 ms 33364 KB Output is correct
3 Correct 14 ms 33308 KB Output is correct
4 Correct 14 ms 33344 KB Output is correct
5 Correct 20 ms 33620 KB Output is correct
6 Correct 1575 ms 103564 KB Output is correct
7 Correct 2004 ms 103688 KB Output is correct
8 Correct 2194 ms 103892 KB Output is correct
9 Runtime error 2355 ms 207892 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 33364 KB Output is correct
2 Correct 14 ms 33360 KB Output is correct
3 Correct 14 ms 33364 KB Output is correct
4 Correct 14 ms 33340 KB Output is correct
5 Correct 14 ms 33308 KB Output is correct
6 Correct 146 ms 36104 KB Output is correct
7 Correct 253 ms 42648 KB Output is correct
8 Correct 1145 ms 101284 KB Output is correct
9 Correct 1202 ms 101280 KB Output is correct
10 Correct 1166 ms 101316 KB Output is correct
11 Correct 1366 ms 101276 KB Output is correct
12 Correct 1218 ms 101276 KB Output is correct
13 Correct 1172 ms 101276 KB Output is correct
14 Correct 1795 ms 101280 KB Output is correct
15 Correct 18 ms 33364 KB Output is correct
16 Correct 17 ms 33364 KB Output is correct
17 Correct 15 ms 33364 KB Output is correct
18 Correct 14 ms 33364 KB Output is correct
19 Correct 15 ms 33364 KB Output is correct
20 Correct 22 ms 33780 KB Output is correct
21 Correct 111 ms 39612 KB Output is correct
22 Correct 16 ms 33384 KB Output is correct
23 Correct 22 ms 33760 KB Output is correct
24 Correct 121 ms 39684 KB Output is correct
25 Correct 133 ms 39592 KB Output is correct
26 Correct 206 ms 39752 KB Output is correct
27 Correct 107 ms 39732 KB Output is correct
28 Correct 233 ms 44940 KB Output is correct
29 Runtime error 3127 ms 208812 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -