| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1062519 |
2024-08-17T08:12:06 Z |
cloudy |
Wall (IOI14_wall) |
C++17 |
|
591 ms |
14820 KB |
#include <bits/stdc++.h>
#define fastIO \
ios_base::sync_with_stdio(false); \
cin.tie(nullptr)
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define mp make_pair
#define f first
#define s second
#define pb push_back
const ll INF = 1000000000000000000;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
string stepDir = "URDL";
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << '{';
string sep;
for (const auto &x : v) os << sep << x, sep = ", ";
return os << '}';
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
return os << '(' << p.first << ", " << p.second << ')';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
cerr << ' ' << H;
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
#define MOD 1000000007
struct segtree {
int size;
const ll NO_OP_MAX = LLONG_MIN;
const ll NO_OP_MIN = LLONG_MAX;
vector<ll> max_operations, min_operations, values;
ll modify_op_max(ll a, ll b) {
if (b == NO_OP_MAX) return a;
return max(a, b);
}
ll modify_op_min(ll a, ll b) {
if (b == NO_OP_MIN) return a;
return min(a, b);
}
void apply_mod_op_max(ll &a, ll b) { a = modify_op_max(a, b); }
void apply_mod_op_min(ll &a, ll b) { a = modify_op_min(a, b); }
void init(int n) {
size = 1;
while (size < n) size *= 2;
max_operations.assign(2 * size, NO_OP_MAX);
min_operations.assign(2 * size, NO_OP_MIN);
values.assign(2 * size, 0LL);
}
void propagate(int x, int lx, int rx) {
if (rx - lx == 1) return; // leaves
int m = (lx + rx) / 2;
apply_mod_op_max(max_operations[2 * x + 1], max_operations[x]);
apply_mod_op_max(values[2 * x + 1], max_operations[x]);
apply_mod_op_min(min_operations[2 * x + 1], min_operations[x]);
apply_mod_op_min(values[2 * x + 1], min_operations[x]);
apply_mod_op_max(max_operations[2 * x + 2], max_operations[x]);
apply_mod_op_max(values[2 * x + 2], max_operations[x]);
apply_mod_op_min(min_operations[2 * x + 2], min_operations[x]);
apply_mod_op_min(values[2 * x + 2], min_operations[x]);
max_operations[x] = NO_OP_MAX;
min_operations[x] = NO_OP_MIN;
}
void op_max(int l, int r, ll v, int x, int lx, int rx) {
propagate(x, lx, rx);
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
apply_mod_op_max(max_operations[x], v);
apply_mod_op_max(values[x], v);
return;
}
int m = (lx + rx) / 2;
op_max(l, r, v, 2 * x + 1, lx, m);
op_max(l, r, v, 2 * x + 2, m, rx);
values[x] = min(values[2 * x + 1], values[2 * x + 2]);
}
void op_min(int l, int r, ll v, int x, int lx, int rx) {
propagate(x, lx, rx);
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
apply_mod_op_min(min_operations[x], v);
apply_mod_op_min(values[x], v);
return;
}
int m = (lx + rx) / 2;
op_min(l, r, v, 2 * x + 1, lx, m);
op_min(l, r, v, 2 * x + 2, m, rx);
values[x] = min(values[2 * x + 1], values[2 * x + 2]);
}
void op_max(int l, int r, ll v) { op_max(l, r, v, 0, 0, size); }
void op_min(int l, int r, ll v) { op_min(l, r, v, 0, 0, size); }
ll get(int l, int r, int x, int lx, int rx) {
propagate(x, lx, rx);
if (lx >= r || rx <= l) return LLONG_MAX - 1;
if (lx >= l && rx <= r) return values[x];
int m = (lx + rx) / 2;
ll s1 = get(l, r, 2 * x + 1, lx, m);
ll s2 = get(l, r, 2 * x + 2, m, rx);
return min(s1, s2);
}
ll get(int l, int r) { return get(l, r, 0, 0, size); }
};
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout << fixed << setprecision(10);
// ll n, m;
// cin >> n >> m;
// segtree seg;
// seg.init(n + 2);
// while (m--) {
// int t, l, r;
// ll x;
// cin >> t >> l >> r >> x;
// r++;
// if (t == 1)
// seg.op_max(l, r, x);
// else
// seg.op_min(l, r, x);
// }
// for (int i = 0; i < n; i++) cout << seg.get(i, i + 1) << "\n";
// }
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
segtree seg;
seg.init(n + 2);
for (int i = 0; i < k; i++) {
int t = op[i], l = left[i], r = right[i], x = height[i];
r++;
if (t == 1)
seg.op_max(l, r, x);
else
seg.op_min(l, r, x);
}
for (int i = 0; i < n; i++) finalHeight[i] = seg.get(i, i + 1);
}
Compilation message
wall.cpp: In member function 'void segtree::propagate(int, int, int)':
wall.cpp:71:9: warning: unused variable 'm' [-Wunused-variable]
71 | int m = (lx + rx) / 2;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
98 ms |
8160 KB |
Output is correct |
| 3 |
Correct |
184 ms |
5212 KB |
Output is correct |
| 4 |
Correct |
591 ms |
14820 KB |
Output is correct |
| 5 |
Correct |
309 ms |
14672 KB |
Output is correct |
| 6 |
Correct |
305 ms |
14792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
