oj.uz

Submission #1042675

# Submission time Handle Problem Language Result Execution time Memory
1042675 2024-08-03T09:31:15 Z Soumya1 Comparing Plants (IOI20_plants) C++17
5 / 100
 472 ms 43856 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
const int mxN = 2e5 + 5;
int t[4 * mxN], lazy[4 * mxN];
void apply(int x, int v) {
	t[x] += v;
	lazy[x] += v;
}
void push(int x, int lx, int rx) {
	if (lx == rx) return;
	apply(x << 1, lazy[x]);
	apply(x << 1 | 1, lazy[x]);
	lazy[x] = 0;
}
void update(int x, int lx, int rx, int l, int r, int v) {
	if (lazy[x]) push(x, lx, rx);
	if (l > rx || lx > r) return;
	if (l <= lx && r >= rx) {
		apply(x, v);
		return;
	}
	int mx = (lx + rx) >> 1;
	update(x << 1, lx, mx, l, r, v);
	update(x << 1 | 1, mx + 1, rx, l, r, v);
	t[x] = min(t[x << 1], t[x << 1 | 1]);
}
int query(int x, int lx, int rx, int l, int r) {
	if (lazy[x]) push(x, lx, rx);
	if (l > rx || lx > r || t[x]) return -1;
	if (lx == rx) return lx;
	int mx = (lx + rx) >> 1;
	int y = query(x << 1, lx, mx, l, r);
	if (y != -1) return y;
	return query(x << 1 | 1, mx + 1, rx, l, r);
}
int min_query(int x, int lx, int rx, int l, int r) {
	if (lazy[x]) push(x, lx, rx);
	if (l > rx || lx > r) return 1e9;
	if (l <= lx && r >= rx) return t[x];
	int mx = (lx + rx) >> 1;
	return min(min_query(x << 1, lx, mx, l, r), min_query(x << 1 | 1, mx + 1, rx, l, r));
}
int val[mxN], pos[mxN], cur;
int n, k;
void dfs(int u) {
	vector<pair<int, int>> ranges;
	if (u >= k + 1) ranges = {{u - k, u - 1}};
	else if (u == 1) ranges = {{n - k + 1, n}};
	else ranges = {{max(1, u - k), u - 1}, {n - k + u, n}};
	for (auto [l, r] : ranges) {
		int idx = query(1, 1, n, l, r);
		while (idx != -1) {
			dfs(idx);
			idx = query(1, 1, n, l, r);
		}
	}
	for (auto [l, r] : ranges) {
		update(1, 1, n, l, r, -1);
	}
	pos[cur] = u;
	val[u] = cur--;
	update(1, 1, n, u, u, 1e9);
}
const int lg = 20;
int L[mxN][lg], R[mxN][lg];
void init(int K, vector<int> r) {
	k = K - 1, n = r.size();
	cur = n;
	for (int i = 0; i < n; i++) {
		update(1, 1, n, i + 1, i + 1, r[i]);
	}
	while (true) {
		int i = query(1, 1, n, 1, n);
		if (i != -1) dfs(i);
		else break;
	}
	for (int i = 1; i <= n; i++) {
		update(1, 1, n, i, i, -min_query(1, 1, n, i, i) + 1e9);
	}
	val[0] = n + 1, pos[n + 1] = 0;
	for (int i = n; i >= 1; i--) {
		int p = pos[i];
		int mn = min(min_query(1, 1, n, max(p - k, 1), p - 1), min_query(1, 1, n, min(n - k + p, n + 1), n));
		L[pos[i]][0] = (mn == 1e9 ? 0 : pos[mn]);
		mn = min(min_query(1, 1, n, p + 1, min(n, p + k)), min_query(1, 1, n, 1, p + k - n));
		R[pos[i]][0] = (mn == 1e9 ? 0 : pos[mn]);
		update(1, 1, n, pos[i], pos[i], -1e9 + i);
	}
	val[n + 1] = n + 1;
	R[n + 1][0] = n + 1;
	// for (int i = 1; i <= n; i++) cout << val[i] << " "; cout << endl;
	// for (int i = 1; i <= n; i++) cout << L[i][0] << " " << R[i][0] << endl;
	for (int i = 1; i <= n; i++) {
		if (!R[i][0]) R[i][0] = n + 1;
	}
	for (int j = 1; j < lg; j++) {
		for (int i = 0; i <= n + 1; i++) {
			L[i][j] = L[L[i][j - 1]][j - 1];
			R[i][j] = R[R[i][j - 1]][j - 1];
		}
	}
}
bool Lpath(int x, int y) {
	if (x > y) {
		for (int j = lg - 1; j >= 0; j--) {
			if (L[x][j] >= y && L[x][j] <= x) x = L[x][j];
		}
	} else {
		for (int j = lg - 1; j >= 0; j--) {
			if (L[x][j] >= 1 && L[x][j] <= x) x = L[x][j];
		}
		x = L[x][0];
		for (int j = lg - 1; j >= 0; j--) {
			if (L[x][j] >= y && L[x][j] <= x) x = L[x][j];
		}
	}
	return (val[x] <= val[y] && (x - y + n) % n <= k);
}
bool Rpath(int x, int y) {
	if (x < y) {
		for (int j = lg - 1; j >= 0; j--) {
			if (R[x][j] <= y && R[x][j] >= x) x = R[x][j];
		}
	} else {
		for (int j = lg - 1; j >= 0; j--) {
			if (R[x][j] <= n && R[x][j] >= x) x = R[x][j];
		}
		x = R[x][0];
		for (int j = lg - 1; j >= 0; j--) {
			if (R[x][j] <= y && R[x][j] >= x) x = R[x][j];
		}
	}
	return (val[x] <= val[y] && (y - x + n) % n <= k);
}
int compare_plants(int x, int y) {
	x++, y++;
	if (Lpath(x, y) || Rpath(x, y)) return -1;
	if (Lpath(y, x) || Rpath(y, x)) return 1;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 41 ms 3060 KB Output is correct
7 Correct 83 ms 9200 KB Output is correct
8 Correct 380 ms 43640 KB Output is correct
9 Correct 378 ms 43856 KB Output is correct
10 Correct 390 ms 43812 KB Output is correct
11 Correct 472 ms 43760 KB Output is correct
12 Correct 386 ms 43856 KB Output is correct
13 Correct 365 ms 43664 KB Output is correct
14 Correct 365 ms 43636 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 60 ms 3492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 672 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 41 ms 3060 KB Output is correct
7 Correct 83 ms 9200 KB Output is correct
8 Correct 380 ms 43640 KB Output is correct
9 Correct 378 ms 43856 KB Output is correct
10 Correct 390 ms 43812 KB Output is correct
11 Correct 472 ms 43760 KB Output is correct
12 Correct 386 ms 43856 KB Output is correct
13 Correct 365 ms 43664 KB Output is correct
14 Correct 365 ms 43636 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Halted 0 ms 0 KB -