| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 761260 |
2023-06-19T12:11:37 Z |
coloboxx |
Wall (IOI14_wall) |
C++17 |
|
849 ms |
112964 KB |
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse2,sse3,ssse3,sse4,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define point pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define show(x) cerr << (#x) << " = " << x << '\n'
#define print(x) if (1) {cerr << (#x) << " = "; for (auto it : x) \
cerr << it << ' '; cerr << '\n';}
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0)
const int N = 1 << 21;
const int K = 1 << 19;
const int S = 1e7 + 64;
const int INF = 2e9 + 64;
const ll MAX = 2e18 + 64;
const int LOG = 21;
const int MOD = 1e9 + 7; //998244353;
const int P = 79;
using namespace std;
vector<int> t[4 * K];
template <class T, T (*F) (T, T)>
struct segtree{
int n;
T def{};
vector<T> t;
segtree(int n, T def, vector<T> v = {}) : n(n), def(def) {
t.assign(2 * n, def);
for (int i = 0; i < min(n, (int)v.size()); ++i)
t[i + n] = v[i];
for (int i = n - 1; i > 0; --i)
t[i] = F(t[i << 1], t[i << 1 | 1]);
}
inline void update(int p, T val) {
for (t[p += n] = val; p > 1; p >>= 1)
t[p >> 1] = F(t[p], t[p ^ 1]);
}
inline T query(int l, int r) {
T res = def;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = F(res, t[l++]);
if (r & 1) res = F(res, t[--r]);
}
return res;
}
};
int n, k, ptr = 0;
bool used[N];
int par[N], label[N], inv[2 * K], seg[N];
void add_segment(int l, int r, int id) {
for (l += ptr, r += ptr + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) t[l].pb(id), ++l;
if (r & 1) --r, t[r].pb(id);
}
}
int Min(int x, int y) {
return min(x, y);
}
int Max(int x, int y) {
return max(x, y);
}
segtree<int, &Min> tmin(K, INF);
segtree<int, &Max> tmax(K, -INF);
int norm(int l, int r, int x) {
if (x < l) return l;
if (x > r) return r;
return x;
}
void dfs(int v, int mx_id, int o[], int h[], int ans[]) {
// show(v);
for (int id : t[v]) {
mx_id = max(mx_id, id);
if (o[id] == 2)
tmin.update(id, h[id]);
else
tmax.update(id, h[id]);
}
if (v >= ptr) {
int tl = inv[v - ptr];
assert(tl != -1);
if (mx_id == -INF) {
ans[tl] = 0;
}
else {
int lb = -1, rb = mx_id;
while (lb + 1 < rb) {
int mid = (lb + rb) >> 1;
int l = tmax.query(mid, mx_id);
int r = tmin.query(mid, mx_id);
(l <= r ? rb : lb) = mid;
}
int pos = rb;
int l = tmax.query(pos, mx_id);
int r = tmin.query(pos, mx_id);
// show(l), show(r);
if (pos == 0)
ans[tl] = norm(l, r, 0);
else {
// int pl = tmax.query(pos - 1, pos - 1);
int pr = tmin.query(pos - 1, pos - 1);
// if (max(l, pl) <= min(r, pr))
// exit(0);
// show(pl), show(pr);
if (pr < l)
ans[tl] = l;
else
ans[tl] = r;
}
//cerr << "BBB\n";
}
// for (int j = 0; j < k; ++j)
// cerr << "{" << tmax.query(j, j) << ", " << tmin.query(j, j) << "}\n";
}
else {
dfs(v << 1, mx_id, o, h, ans);
dfs(v << 1 | 1, mx_id, o, h, ans);
}
for (int id : t[v]) {
if (o[id] == 2)
tmin.update(id, INF);
else
tmax.update(id, -INF);
}
}
void buildWall(int _n, int _k, int op[], int left[], int right[], int height[], int finalHeight[]) {
n = _n, k = _k;
fill(inv, inv + 2 * K, -1);
for (int i = 0; i < k; ++i)
used[left[i]] = used[right[i]] = true, ++seg[left[i]], --seg[right[i] + 1];
for (int i = 1; i < n; ++i)
seg[i] += seg[i - 1];
par[0] = 0;
for (int i = 1; i < n; ++i)
if (!used[i] && (seg[i] == 0) == (seg[i - 1] == 0))
par[i] = par[i - 1];
else
par[i] = i;
for (int i = 0; i < n; ++i)
if (used[i])
label[i] = ptr++, inv[label[i]] = i;
for (int i = 0; i < k; ++i)
add_segment(label[left[i]], label[right[i]], i);
dfs(1, -INF, op, height, finalHeight);
for (int i = 0; i < n; ++i)
if (!used[i])
finalHeight[i] = finalHeight[par[i]];
}
#include "wall.h"
// int main()
// {
// int n;
// int k;
// // for (int i = 0; i < 10; ++i)
// // show(tmin.query(i, i));
// // show(tmin.def);
// int i, j;
// int status = 0;
// status = scanf("%d%d", &n, &k);
// assert(status == 2);
// int* op = (int*)calloc(sizeof(int), k);
// int* left = (int*)calloc(sizeof(int), k);
// int* right = (int*)calloc(sizeof(int), k);
// int* height = (int*)calloc(sizeof(int), k);
// int* finalHeight = (int*)calloc(sizeof(int), n);
// for (i = 0; i < k; i++){
// status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
// assert(status == 4);
// }
// buildWall(n, k, op, left, right, height, finalHeight);
// for (j = 0; j < n; j++)
// printf("%d\n", finalHeight[j]);
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
61908 KB |
Output is correct |
| 2 |
Correct |
34 ms |
62036 KB |
Output is correct |
| 3 |
Correct |
34 ms |
61916 KB |
Output is correct |
| 4 |
Incorrect |
42 ms |
62604 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
61800 KB |
Output is correct |
| 2 |
Correct |
161 ms |
71888 KB |
Output is correct |
| 3 |
Correct |
233 ms |
79472 KB |
Output is correct |
| 4 |
Correct |
849 ms |
112964 KB |
Output is correct |
| 5 |
Correct |
320 ms |
80776 KB |
Output is correct |
| 6 |
Incorrect |
327 ms |
80628 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
61784 KB |
Output is correct |
| 2 |
Correct |
36 ms |
62020 KB |
Output is correct |
| 3 |
Correct |
35 ms |
61936 KB |
Output is correct |
| 4 |
Incorrect |
43 ms |
62776 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
61848 KB |
Output is correct |
| 2 |
Correct |
35 ms |
62028 KB |
Output is correct |
| 3 |
Correct |
43 ms |
61908 KB |
Output is correct |
| 4 |
Incorrect |
42 ms |
62564 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
