| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 257630 |
2020-08-04T13:44:53 Z |
Haunted_Cpp |
Wall (IOI14_wall) |
C++17 |
|
1 ms |
512 KB |
/**
* author: Haunted_Cpp
**/
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
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 T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) 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 debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif
const int UP = 1e9;
class SegmentTree {
private:
struct Node {
int mn;
int mx;
int aumentar;
int diminuir;
Node () {
mn = mx = 0;
aumentar = -1;
diminuir = UP;
}
void merge(Node l, Node r) {
mn = min(l.mn, r.mn);
mx = max(l.mx, r.mx);
}
};
const int LO, HI;
vector<Node> seg;
void push_aumentar(int l, int r, int node) {
if (seg[node].aumentar == -1) return;
seg[node].mn = max(seg[node].mn, seg[node].aumentar);
seg[node].mx = max(seg[node].mx, seg[node].mn);
if (l != r) {
seg[2 * node + 1].aumentar = max(seg[2 * node + 1].aumentar, seg[node].aumentar);
seg[2 * node + 2].aumentar = max(seg[2 * node + 2].aumentar, seg[node].aumentar);
if (seg[2 * node + 1].aumentar >= seg[2 * node + 1].diminuir) {
seg[2 * node + 1].diminuir = seg[2 * node + 1].aumentar;
}
if (seg[2 * node + 2].aumentar >= seg[2 * node + 2].diminuir) {
seg[2 * node + 2].diminuir = seg[2 * node + 2].aumentar;
}
}
seg[node].aumentar = -1;
}
void push_diminuir(int l, int r, int node) {
if (seg[node].diminuir == UP) return;
seg[node].mx = min(seg[node].mx, seg[node].diminuir);
seg[node].mn = min(seg[node].mn, seg[node].mx);
if (l != r) {
seg[2 * node + 1].diminuir = min(seg[2 * node + 1].diminuir, seg[node].diminuir);
seg[2 * node + 2].diminuir = min(seg[2 * node + 2].diminuir, seg[node].diminuir);
if (seg[2 * node + 1].diminuir <= seg[2 * node + 1].aumentar) {
seg[2 * node + 1].aumentar = seg[2 * node + 1].diminuir;
}
if (seg[2 * node + 2].diminuir <= seg[2 * node + 2].aumentar) {
seg[2 * node + 2].aumentar = seg[2 * node + 2].diminuir;
}
}
seg[node].diminuir = UP;
}
void pushdown(int l, int r, int node) {
push_aumentar(l, r, node);
push_diminuir(l, r, node);
}
void range_update(int ql, int qr, int delta, int l, int r, int node, bool task) {
pushdown(l, r, node);
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
if(task) seg[node].aumentar = delta;
else seg[node].diminuir = delta;
pushdown(l, r, node);
return;
}
const int mid = l + (r - l) / 2;
range_update(ql, qr, delta, l, mid, 2 * node + 1, task);
range_update(ql, qr, delta, mid + 1, r, 2 * node + 2, task);
seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
}
void print(int l, int r, int node) {
pushdown(l, r, node);
if (l == r) {
ans.emplace_back(seg[node].mn);
return;
}
const int mid = l + (r - l) / 2;
print(l, mid, 2 * node + 1);
print(mid + 1, r, 2 * node + 2);
}
public:
SegmentTree(int n) : LO(0), HI(n - 1) {
seg.resize(4 * n);
}
void range_update(int ql, int qr, int delta, bool task) {
range_update(ql, qr, delta, LO, HI, 0, task);
}
vector<int> ans;
void print_ans() {
print(LO, HI, 0);
}
};
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]) {
ios::sync_with_stdio(0);
cin.tie(0);
SegmentTree seg(n);
for (int i = 0; i < k; i++) {
int task = op[i];
int lo = left[i];
int hi = right[i];
int delta = height[i];
if (task == 1) {
seg.range_update(lo, hi, delta, true);
} else {
seg.range_update(lo, hi, delta, false);
}
}
for (int i = 0; i < n; i++) finalHeight[i] = seg.ans[i];
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
