| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 288682 |
2020-09-01T18:40:12 Z |
emil_physmath |
Wall (IOI14_wall) |
C++17 |
|
270 ms |
48320 KB |
#include "wall.h"
#include <algorithm>
#include <iostream>
#include <random>
#include <chrono>
using namespace std;
using llong = long long;
#define BUGO(x) cerr << #x << " = " << (x) << '\n';
#define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';}
#ifndef MANSON
#define BUGO(x)
#define BUGOARR(x)
#endif
ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
out << "{" << p.first << ", " << p.second << "}";
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
const int maxN = 100'005;
const int maxH = 100'000;
int mind[4 * maxN], maxu[4 * maxN];
void SetD(int v, int vl, int vr, int i, int x)
{
if (vl == vr) {
mind[v] = x;
return;
}
int vm = vl + (vr - vl) / 2;
if (i <= vm) SetD(v * 2, vl, vm, i, x);
else SetD(v * 2 + 1, vm + 1, vr, i, x);
mind[v] = min(mind[v * 2], mind[v * 2 + 1]);
}
int LastLess(int v, int vl, int vr, int x)
{
if (vl == vr)
return vr;
int vm = vl + (vr - vl) / 2;
if (mind[v * 2 + 1] >= x)
return LastLess(v * 2, vl, vm, x);
return LastLess(v * 2 + 1, vm + 1, vr, x);
}
void SetU(int v, int vl, int vr, int i, int x)
{
if (vl == vr) {
maxu[v] = x;
return;
}
int vm = vl + (vr - vl) / 2;
if (i <= vm) SetU(v * 2, vl, vm, i, x);
else SetU(v * 2 + 1, vm + 1, vr, i, x);
maxu[v] = max(maxu[v * 2], maxu[v * 2 + 1]);
}
int Max(int v, int vl, int vr, int l, int r) {
if (l > vr || vl > r) return -1;
if (l <= vl && vr <= r) return maxu[v];
int vm = vl + (vr - vl) / 2;
return max(Max(v * 2, vl, vm, l, r), Max(v * 2 + 1, vm + 1, vr, l, r));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[])
{
struct Upd {
bool add;
char dir;
int time;
int i, hei;
};
vector<Upd> upd;
upd.push_back({true, 'D', -1, -1, 0});
for (int i = 0; i < k; ++i)
{
upd.push_back({true, op[i] == 1 ? 'U' : 'D', left[i], i, height[i]});
upd.push_back({false, op[i] == 1 ? 'U' : 'D', right[i] + 1, i, height[i]});
}
sort(upd.begin(), upd.end(), [](const Upd& l, const Upd& r) {
return l.time < r.time;
});
for (int i = -1; i < k; ++i)
SetD(1, -1, k - 1, i, maxH + 1);
for (int i = 0; i < k; ++i)
SetU(1, 0, k - 1, i, -1);
for (int i = 0, ind = 0; i < n; ++i)
{
while (ind < upd.size() && upd[ind].time <= i)
{
Upd& u = upd[ind];
if (u.dir == 'D')
{
if (u.add)
SetD(1, -1, k - 1, u.i, u.hei);
else
SetD(1, -1, k - 1, u.i, maxH + 1);
}
else
{
if (u.add)
SetU(1, 0, k - 1, u.i, u.hei);
else
SetU(1, 0, k - 1, u.i, -1);
}
++ind;
}
ans[i] = 0;
int lans = 1, rans = maxH;
while (lans <= rans)
{
int cans = (lans + rans) / 2;
int l = LastLess(1, -1, k - 1, cans);
if (l + 1 <= k - 1 && Max(1, 0, k - 1, l + 1, k - 1) >= cans) {
ans[i] = cans;
lans = cans + 1;
}
else
rans = cans - 1;
}
}
}
Compilation message
wall.cpp:11: warning: "BUGO" redefined
11 | #define BUGO(x)
|
wall.cpp:8: note: this is the location of the previous definition
8 | #define BUGO(x) cerr << #x << " = " << (x) << '\n';
|
wall.cpp:12: warning: "BUGOARR" redefined
12 | #define BUGOARR(x)
|
wall.cpp:9: note: this is the location of the previous definition
9 | #define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';}
|
wall.cpp:14:46: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
14 | ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
| ^~~~
wall.cpp:14:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
14 | ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
| ^~~~
wall.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::pair<_T1, _T2>&)':
wall.cpp:16:1: warning: no return statement in function returning non-void [-Wreturn-type]
16 | }
| ^
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<buildWall(int, int, int*, int*, int*, int*, int*)::Upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while (ind < upd.size() && upd[ind].time <= i)
| ~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
768 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
27 ms |
896 KB |
Output is correct |
| 5 |
Correct |
30 ms |
896 KB |
Output is correct |
| 6 |
Correct |
30 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
264 ms |
48320 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
768 KB |
Output is correct |
| 3 |
Correct |
3 ms |
544 KB |
Output is correct |
| 4 |
Correct |
34 ms |
896 KB |
Output is correct |
| 5 |
Correct |
30 ms |
896 KB |
Output is correct |
| 6 |
Correct |
30 ms |
896 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Runtime error |
268 ms |
48320 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
896 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
27 ms |
896 KB |
Output is correct |
| 5 |
Correct |
30 ms |
896 KB |
Output is correct |
| 6 |
Correct |
30 ms |
896 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Runtime error |
270 ms |
48320 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
