| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 596467 | Elias | Wall (IOI14_wall) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifndef _DEBUG
#include "wall.h"
#endif
template <class T>
istream &operator>>(istream &in, vector<T> &a)
{
for (auto &x : a)
in >> x;
return in;
}
int minusMin(int a, int b)
{
if (a == -1)
return b;
if (b == -1)
return a;
return min(a, b);
}
int minusMax(int a, int b)
{
if (a == -1)
return b;
if (b == -1)
return a;
return max(a, b);
}
struct Node
{
int low = -1;
int high = -1;
bool first = 0;
void Apply(Node update)
{
if (this->low == -1 && this->high == -1)
{
*this = update;
return;
}
if (update.low == -1 && update.high == -1)
return;
low = minusMax(low, update.low);
high = minusMin(high, update.high);
if (low > high && high != -1)
{
low = high = ((low == update.low) ? update.low : update.high);
}
bool a = low == update.low && low != -1;
bool b = high == update.high && high != -1;
if (a && b)
first = update.low;
else if (a)
first = 0;
else if (b)
first = 1;
}
};
Node emp = {-1, -1, 0};
vector<Node> b;
void updateRange(int l, int r, int i, int ul, int ur, Node up)
{
if (l >= ur || r <= ul)
return;
if (l >= ul && r <= ur)
{
b[i].Apply(up);
return;
}
b[i * 2 + 1].Apply(b[i]);
b[i * 2 + 2].Apply(b[i]);
b[i] = emp;
int m = (l + r) / 2;
updateRange(l, m, i * 2 + 1, ul, ur, up);
updateRange(m, r, i * 2 + 2, ul, ur, up);
}
void extractValues(int l, int r, int i, vector<int> &a)
{
if (l + 1 == r)
{
a[l] = max(b[i].low, 0);
return;
}
b[i * 2 + 1].Apply(b[i]);
b[i * 2 + 2].Apply(b[i]);
b[i] = emp;
int m = (l + r) / 2;
extractValues(l, m, i * 2 + 1, a);
extractValues(m, r, i * 2 + 2, a);
}
void buildWall(int n, int k, int[] op, int[] left, int[] right, int[] height, int[] finalHeight)
{
b = vector<Node>(n * 4, emp);
for (int i = 0; i < k; i++)
updateRange(0, n, 0, left[i], right[i] + 1, ((op[i] == 1) ? Node{height[i], -1, 0} : Node{-1, height[i], 1}));
extractValues(0, n, 0, finalHeight);
}
#ifdef _DEBUG
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, k;
cin >> n >> k;
vector<int> op, left, right, height;
op = left = right = height = vector<int>(k);
cin >> op >> left >> right >> height;
vector<int> finalHeight(n);
buildWall(n, k, op, left, right, height, finalHeight);
for (int &x : finalHeight)
cout << x << " ";
cout << "\n";
}
#endif