oj.uz

Submission #935962

# Submission time Handle Problem Language Result Execution time Memory
935962 2024-02-29T20:03:14 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 79424 KB 
#include <bits/stdc++.h>
#include "plants.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) {
		// cout << fnd[i].x << ' ';
		fnd[i].x += x;
		fndl[i] += x;
		// cout << fnd[i].x << ' ' << i << '\n';
		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) {
		// cout << fnd[i].x << ' ' << fnd[i].y << ' ' << i << '\n';
		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++) {
    	fnd[i + N - 1].y = i;
    }
    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 - 1);
    	// cout << value << ' ' << i << '\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;
    		if (tmp1 == tmp2) {
    			used2[tmp2] = 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 < n) {
    		set_seg(i + 1, i + k - 1, i, st2, lz2);
    		add_seg(i + 1, i + k - 1, -1);
    	} else {
    		set_seg(i + 1, n - 1, i, st2, lz2);
    		set_seg(0, i + k - 1 - n, i, st2, lz2);
    		add_seg(i + 1, n - 1, -1);
    		add_seg(0, i + k - 1 - n, -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);
    		// cout << get_min(2, 2).x << '\n';
    		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) {
    			// cout << j << ' ';
    			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);
				}
    		}
    		// cout << '\n';
    	}
        // 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;
        //     }
        // }
        // 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);
        // cout << get_min(i, i).x << '\n';
        // 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:101:17: warning: unused variable 'last' [-Wunused-variable]
  101 |     int ok = 0, last, lev = n, iter = 0;
      |                 ^~~~
plants.cpp:101:23: warning: unused variable 'lev' [-Wunused-variable]
  101 |     int ok = 0, last, lev = n, iter = 0;
      |                       ^~~
plants.cpp:101:32: warning: unused variable 'iter' [-Wunused-variable]
  101 |     int ok = 0, last, lev = n, iter = 0;
      |                                ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 45404 KB Output is correct
2 Correct 9 ms 43356 KB Output is correct
3 Correct 9 ms 43300 KB Output is correct
4 Correct 9 ms 43356 KB Output is correct
5 Correct 9 ms 43356 KB Output is correct
6 Correct 59 ms 46168 KB Output is correct
7 Correct 116 ms 47276 KB Output is correct
8 Correct 554 ms 56920 KB Output is correct
9 Correct 616 ms 57240 KB Output is correct
10 Correct 1231 ms 57084 KB Output is correct
11 Correct 2713 ms 58320 KB Output is correct
12 Execution timed out 4024 ms 57692 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45404 KB Output is correct
2 Correct 10 ms 43356 KB Output is correct
3 Correct 10 ms 45232 KB Output is correct
4 Runtime error 38 ms 79184 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45404 KB Output is correct
2 Correct 10 ms 43356 KB Output is correct
3 Correct 10 ms 45232 KB Output is correct
4 Runtime error 38 ms 79184 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43356 KB Output is correct
2 Runtime error 37 ms 79196 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 45404 KB Output is correct
2 Correct 10 ms 43356 KB Output is correct
3 Correct 10 ms 43188 KB Output is correct
4 Correct 9 ms 43356 KB Output is correct
5 Runtime error 38 ms 79196 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 45400 KB Output is correct
2 Correct 9 ms 43304 KB Output is correct
3 Correct 12 ms 43356 KB Output is correct
4 Correct 10 ms 43356 KB Output is correct
5 Runtime error 39 ms 79424 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 45404 KB Output is correct
2 Correct 9 ms 43356 KB Output is correct
3 Correct 9 ms 43300 KB Output is correct
4 Correct 9 ms 43356 KB Output is correct
5 Correct 9 ms 43356 KB Output is correct
6 Correct 59 ms 46168 KB Output is correct
7 Correct 116 ms 47276 KB Output is correct
8 Correct 554 ms 56920 KB Output is correct
9 Correct 616 ms 57240 KB Output is correct
10 Correct 1231 ms 57084 KB Output is correct
11 Correct 2713 ms 58320 KB Output is correct
12 Execution timed out 4024 ms 57692 KB Time limit exceeded
13 Halted 0 ms 0 KB -