oj.uz

Submission #935960

# Submission time Handle Problem Language Result Execution time Memory
935960 2024-02-29T20:01:14 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 79384 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 43196 KB Output is correct
3 Correct 9 ms 43356 KB Output is correct
4 Correct 9 ms 43356 KB Output is correct
5 Correct 10 ms 43436 KB Output is correct
6 Correct 56 ms 46156 KB Output is correct
7 Correct 111 ms 47188 KB Output is correct
8 Correct 551 ms 59988 KB Output is correct
9 Correct 613 ms 60064 KB Output is correct
10 Correct 1227 ms 60484 KB Output is correct
11 Correct 2517 ms 61324 KB Output is correct
12 Execution timed out 4049 ms 60740 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 45404 KB Output is correct
2 Correct 10 ms 43356 KB Output is correct
3 Correct 10 ms 45404 KB Output is correct
4 Runtime error 38 ms 79188 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 10 ms 45404 KB Output is correct
2 Correct 10 ms 43356 KB Output is correct
3 Correct 10 ms 45404 KB Output is correct
4 Runtime error 38 ms 79188 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 79304 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 9 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 Runtime error 38 ms 79384 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 45404 KB Output is correct
2 Correct 10 ms 43184 KB Output is correct
3 Correct 10 ms 43416 KB Output is correct
4 Correct 11 ms 43204 KB Output is correct
5 Runtime error 38 ms 79292 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 43196 KB Output is correct
3 Correct 9 ms 43356 KB Output is correct
4 Correct 9 ms 43356 KB Output is correct
5 Correct 10 ms 43436 KB Output is correct
6 Correct 56 ms 46156 KB Output is correct
7 Correct 111 ms 47188 KB Output is correct
8 Correct 551 ms 59988 KB Output is correct
9 Correct 613 ms 60064 KB Output is correct
10 Correct 1227 ms 60484 KB Output is correct
11 Correct 2517 ms 61324 KB Output is correct
12 Execution timed out 4049 ms 60740 KB Time limit exceeded
13 Halted 0 ms 0 KB -