oj.uz

Submission #935965

# Submission time Handle Problem Language Result Execution time Memory
935965 2024-02-29T20:05:41 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 58448 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);
    	if (value) {
    		exit(1);
    	}
    	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);
    		// if (cnt != 1) {
    		// 	exit(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 9 ms 45404 KB Output is correct
2 Correct 10 ms 43356 KB Output is correct
3 Correct 10 ms 43356 KB Output is correct
4 Correct 10 ms 43356 KB Output is correct
5 Correct 10 ms 43356 KB Output is correct
6 Correct 56 ms 46172 KB Output is correct
7 Correct 111 ms 47440 KB Output is correct
8 Correct 552 ms 56916 KB Output is correct
9 Correct 633 ms 57568 KB Output is correct
10 Correct 1241 ms 57320 KB Output is correct
11 Correct 2654 ms 58448 KB Output is correct
12 Execution timed out 4026 ms 57708 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 45400 KB Output is correct
2 Correct 13 ms 43324 KB Output is correct
3 Correct 10 ms 45400 KB Output is correct
4 Runtime error 8 ms 39260 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 45400 KB Output is correct
2 Correct 13 ms 43324 KB Output is correct
3 Correct 10 ms 45400 KB Output is correct
4 Runtime error 8 ms 39260 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43356 KB Output is correct
2 Runtime error 7 ms 39260 KB Execution failed because the return code was nonzero
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 11 ms 43324 KB Output is correct
3 Correct 10 ms 43332 KB Output is correct
4 Correct 11 ms 43356 KB Output is correct
5 Runtime error 8 ms 39112 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 45404 KB Output is correct
2 Correct 11 ms 43356 KB Output is correct
3 Correct 11 ms 43220 KB Output is correct
4 Correct 10 ms 43356 KB Output is correct
5 Runtime error 8 ms 39260 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 43356 KB Output is correct
4 Correct 10 ms 43356 KB Output is correct
5 Correct 10 ms 43356 KB Output is correct
6 Correct 56 ms 46172 KB Output is correct
7 Correct 111 ms 47440 KB Output is correct
8 Correct 552 ms 56916 KB Output is correct
9 Correct 633 ms 57568 KB Output is correct
10 Correct 1241 ms 57320 KB Output is correct
11 Correct 2654 ms 58448 KB Output is correct
12 Execution timed out 4026 ms 57708 KB Time limit exceeded
13 Halted 0 ms 0 KB -