답안 #935938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935938 2024-02-29T19:29:32 Z EJIC_B_KEDAX 식물 비교 (IOI20_plants) C++17
0 / 100
4000 ms 106868 KB
#include <bits/stdc++.h>
 
#define x first
#define y second

using ll = long long;
 
using namespace std;
 
const int N = 1 << 19;
vector<int> g[N];
int st1[2 * N], st2[2 * N], lz1[2 * N], lz2[2 * N], twin[N], tin[N], tout[N], timer = 1, fndl[2 * N], used1[N], used2[N], fre = N / 2;
pair<int, int> fnd[2 * N];

void push(int i, int st[], int lz[]) {
	if (lz[i] != -1) {
		st[2 * i + 1] = lz[i];
		st[2 * i + 2] = lz[i];
		lz[2 * i + 1] = lz[i];
		lz[2 * i + 2] = lz[i];
		lz[i] = -1;
	}
}

void set_seg(int l, int r, int x, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		st[i] = x;
		lz[i] = x;
		return;
	}
	if (l1 > r || r1 < l) {
		return;
	}
	push(i, st, lz);
	set_seg(l, r, x, st, lz, l1, (l1 + r1) / 2, 2 * i + 1);
	set_seg(l, r, x, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	st[i] = min(st[2 * i + 1], st[2 * i + 2]);
}

int get(int ind, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 == ind && r1 == ind) {
		return st[i];
	}
	if (l1 > ind || r1 < ind) {
		return INT32_MAX;
	}
	push(i, st, lz);
	return min(get(ind, st, lz, l1, (l1 + r1) / 2, 2 * i + 1), get(ind, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}

void push(int i) {
	fnd[2 * i + 1].x += fndl[i];
	fnd[2 * i + 2].x += fndl[i];
	fndl[2 * i + 1] += fndl[i];
	fndl[2 * i + 2] += fndl[i];
	fndl[i] = 0;
}

void add_seg(int l, int r, int x, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		fnd[i].x += x;
		fndl[i] += x;
		return;
	}
	if (l1 > r || r1 < l) {
		return;
	}
	push(i);
	add_seg(l, r, x, l1, (l1 + r1) / 2, 2 * i + 1);
	add_seg(l, r, x, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	fnd[i] = min(fnd[2 * i + 1], fnd[2 * i + 2]);
}

pair<int, int> get_min(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		return fnd[i];
	}
	if (l1 > r || r1 < l) {
		return {INT32_MAX, -1};
	}
	push(i);
	return min(get_min(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get_min(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}

void dfs(int s, int p) {
	tin[s] = timer++;
	for (int i : g[s]) {
		if (i != p) {
			dfs(i, s);
		}
	}
	tout[s] = timer++;
}
 
void init(int k, vector<int> r) {
    int n = r.size();
    int ok = 0, last, lev = n, iter = 0;
    for (int i = 0; i < 2 * N; i++) {
    	st1[i] = -1;
    	st2[i] = -1;
    	lz1[i] = -1;
    	lz2[i] = -1;
    }
    for (int i = 0; i < N; i++) {
    	twin[i] = -1;
    }
    for (int i = 0; i < n; i++) {
    	add_seg(i, i, r[i]);
		if (r[i] == 0) {
			if (i + k > n) {
				add_seg(i + 1, n - 1, 1);
				add_seg(0, i + k - n - 1, 1);
			} else {
				add_seg(i + 1, i + k - 1, 1);
			}
		}
    }
    while (ok < n) {
    	auto [value, i] = get_min(0, n);
    	assert(value == 0);
    	int tmp1 = get(i, st1, lz1), tmp2 = get(i, st2, lz2), cnt = 0;
    	if (tmp1 != -1 && !used1[tmp1]) {
    		g[tmp1].push_back(i);
    		used1[tmp1] = 1;
    		cnt++;
    		if (twin[tmp1] != -1) {
    			twin[i] = fre++;
    			g[twin[tmp1]].push_back(twin[i]);
    			cnt++;
    		}
    	}
    	if (tmp2 != -1 && !used2[tmp2] && !cnt) {
    		g[tmp2].push_back(i);
    		used2[tmp2] = 1;
    		if (twin[tmp2] != -1) {
    			twin[i] = fre++;
    			g[twin[tmp2]].push_back(twin[i]);
    		}
    	} else if (tmp2 != -1 && !used2[tmp2]) {
    		assert(cnt == 1);
    		twin[i] = fre++;
    		g[tmp2].push_back(twin[i]);
    		used2[tmp2] = 1;
    	}
    	if (i >= k - 1) {
    		add_seg(i - k + 1, i - 1, -1);
    		int left = i - k + 1;
    		vector<int> z;
    		while (left <= i - 1 && !get_min(left, i - 1).x) {
    			z.push_back(get_min(left, i - 1).y);
    			left = z.back() + 1;
    		}
    		for (int j : z) {
    			if (j + k > n) {
					add_seg(j + 1, n - 1, 1);
					add_seg(0, j + k - n - 1, 1);
				} else {
					add_seg(j + 1, j + k - 1, 1);
				}
    		}
    		set_seg(i - k + 1, i - 1, i, st1, lz1);
    	} else {
    		add_seg(0, i - 1, -1);
    		set_seg(0, i - 1, i, st1, lz1);
    		add_seg(n + 1 - k + i, n - 1, -1);
    		set_seg(n + 1 - k + i, n - 1, i, st1, lz1);
    		int left = 0;
    		vector<int> z;
    		while (left <= i - 1 && !get_min(left, i - 1).x) {
    			z.push_back(get_min(left, i - 1).y);
    			left = z.back() + 1;
    		}
    		left = n + 1 - k + i;
    		while (left <= n - 1 && !get_min(left, n - 1).x) {
    			z.push_back(get_min(left, n - 1).y);
    			left = z.back() + 1;
    		}
    		for (int j : z) {
    			if (j + k > n) {
					add_seg(j + 1, n - 1, 1);
					add_seg(0, j + k - n - 1, 1);
				} else {
					add_seg(j + 1, j + k - 1, 1);
				}
    		}
    	}
        // for (int j = i - 1; j > i - k; j--) {
        //     if (j >= 0) {
        //         nw[j]--;
        //         tmp1[j] = i;
        //     } else {
        //         nw[j + n]--;
        //         tmp1[j + n] = i;
        //     }
        // }
        if (i + k - 1 < n) {
    		set_seg(i + 1, i + k - 1, i, st2, lz2);
    	} else {
    		set_seg(i + 1, n - 1, i, st2, lz2);
    		set_seg(0, i + k - 1 - n, i, st2, lz2);
    	}
        // for (int j = i + 1; j < i + k; j++) {
        //     if (j < n) {
        //         tmp2[j] = i;
        //     } else {
        //         tmp2[j - n] = i;
        //     }
        // }
        add_seg(i, i, INT32_MAX / 2);
        // nw[i] = INT32_MAX / 2;
    	ok++;
    }
    for (int i = 0; i < N; i++) {
	    if (!tin[i]) {
	    	dfs(i, -1);
	    }
    }
}
 
int compare_plants(int x, int y) {
	vector<int> xx(1, x), yy(1, y);
	if (twin[x] != -1) {
		xx.push_back(twin[x]);
	}
	if (twin[y] != -1) {
		yy.push_back(twin[y]);
	}
	for (int y1 : yy) {
		for (int x1 : xx) {
			if (tin[y1] < tin[x1] && tout[y1] > tin[x1]) {
				return -1;
			}
		}
	}
    // if (clc[y][x]) {
    //     return -1;
    // }
    for (int y1 : xx) {
		for (int x1 : yy) {
			if (tin[y1] < tin[x1] && tout[y1] > tin[x1]) {
				return 1;
			}
		}
	}
    return 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:97:17: warning: unused variable 'last' [-Wunused-variable]
   97 |     int ok = 0, last, lev = n, iter = 0;
      |                 ^~~~
plants.cpp:97:23: warning: unused variable 'lev' [-Wunused-variable]
   97 |     int ok = 0, last, lev = n, iter = 0;
      |                       ^~~
plants.cpp:97:32: warning: unused variable 'iter' [-Wunused-variable]
   97 |     int ok = 0, last, lev = n, iter = 0;
      |                                ^~~~
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4041 ms 106312 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4053 ms 106036 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4053 ms 106036 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4035 ms 106868 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4018 ms 106388 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4030 ms 105756 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4041 ms 106312 KB Time limit exceeded
2 Halted 0 ms 0 KB -