| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 774017 |
2023-07-05T11:03:55 Z |
danikoynov |
Wall (IOI14_wall) |
C++14 |
|
232 ms |
134840 KB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
struct node
{
int max1, max2;
int min1, min2;
node()
{
max1 = 0;
max2 = -inf;
min1 = 0;
min2 = inf;
}
};
node merge_node(node lf, node rf)
{
node nd;
if (lf.max1 == rf.max1)
{
nd.max1 = lf.max1;
nd.max2 = max(lf.max2, rf.max2);
}
else if (lf.max1 > rf.max1)
{
nd.max1 = lf.max1;
nd.max2 = max(lf.max2, rf.max1);
}
else if (lf.max1 < rf.max1)
{
nd.max1 = rf.max1;
nd.max2 = max(lf.max1, rf.max2);
}
if (lf.min1 == rf.min1)
{
nd.min1 = lf.min1;
nd.min2 = min(lf.min2, rf.min2);
}
else if (lf.min1 < rf.min1)
{
nd.min1 = lf.min1;
nd.min2 = min(lf.min2, rf.min1);
}
else if (lf.min1 > rf.min1)
{
nd.min1 = rf.min1;
nd.min2 = min(lf.min1, rf.min2);
}
return nd;
}
const int maxn = 2e6 + 10;
node tree[4 * maxn];
/**void push_min(int root, int val)
{
if (val >= tree[root].max1)
return;
tree[root].max1 = val;
if (tree[root].min1 >= val)
{
tree[root].min1 = val;
tree[root].min2 = inf;
}
else if (tree[root].min2 > val)
{
tree[root].min2 = val;
}
}*/
void push_min(int root, int val)
{
if (val <= tree[root].max2)
{
tree[root].max1 = val;
tree[root].max2 = -inf;
}
else
tree[root].max1 = min(tree[root].max1, val);
if (tree[root].min1 >= val)
{
tree[root].min1 = val;
tree[root].min2 = inf;
}
else if (tree[root].min2 > val)
{
tree[root].min2 = val;
}
}
void push_max(int root, int val)
{
if (val <= tree[root].min1)
return;
tree[root].min1 = val;
if (tree[root].max1 <= val)
{
tree[root].max1 = val;
tree[root].max2 = -inf;
}
else if (tree[root].max2 < val)
{
tree[root].max2 = val;
}
}
void propagate(int root, int left, int right)
{
if (left != right)
{
push_max(root * 2, tree[root].min1);
push_max(root * 2 + 1, tree[root].min1);
push_min(root * 2, tree[root].max1);
push_min(root * 2 + 1, tree[root].max1);
}
}
void update_min(int root, int left, int right, int qleft, int qright, int val)
{
if (left > qright || right < qleft || tree[root].max1 <= val)
return;
if (left >= qleft && right <= qright && tree[root].max2 < val)
{
///cout << "left " << left << " " << right << " " << tree[root].max1 << " " << tree[root].max2 << endl;
push_min(root, val);
return;
}
propagate(root, left, right);
int mid = (left + right) / 2;
update_min(root * 2, left, mid, qleft, qright, val);
update_min(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
void update_max(int root, int left, int right, int qleft, int qright, int val)
{
if (left > qright || right < qleft || tree[root].min1 >= val)
return;
if (left >= qleft && right <= qright && tree[root].min2 > val)
{
push_max(root, val);
///cout << root << " : " << left << " : " << right << endl;
///cout << tree[root].min1 << endl;
//cout << tree[root].max1 << endl;
return;
}
propagate(root, left, right);
int mid = (left + right) / 2;
update_max(root * 2, left, mid, qleft, qright, val);
update_max(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
int arr[maxn];
void dfs(int root, int left, int right)
{
///cout << "dfs " << root << " " << left << " " << right << " " << tree[root].min1 << " " << tree[root].max1 << endl;
if (left == right)
{
arr[left] = tree[root].max1;
return;
}
propagate(root, left, right);
int mid = (left + right) / 2;
dfs(root * 2, left, mid);
dfs(root * 2 + 1, mid + 1, right);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for (int i = 0; i < k; i ++)
{
if (op[i] == 1)
{
update_max(1, 0, n - 1, left[i], right[i], height[i]);
}
else
{
update_min(1, 0, n - 1, left[i], right[i], height[i]);
}
}
dfs(1, 0, n - 1);
for (int i = 0; i < n; i ++)
finalHeight[i] = arr[i];
return;
}
Compilation message
wall.cpp: In function 'void push_max(int, int)':
wall.cpp:103:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
103 | if (val <= tree[root].min1)
| ^~
wall.cpp:106:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
106 | tree[root].min1 = val;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
125516 KB |
Output is correct |
| 2 |
Correct |
48 ms |
125528 KB |
Output is correct |
| 3 |
Correct |
50 ms |
125468 KB |
Output is correct |
| 4 |
Correct |
55 ms |
125644 KB |
Output is correct |
| 5 |
Incorrect |
52 ms |
125640 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
125464 KB |
Output is correct |
| 2 |
Correct |
145 ms |
133316 KB |
Output is correct |
| 3 |
Correct |
103 ms |
128980 KB |
Output is correct |
| 4 |
Correct |
182 ms |
134308 KB |
Output is correct |
| 5 |
Correct |
193 ms |
134800 KB |
Output is correct |
| 6 |
Correct |
232 ms |
134840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
125412 KB |
Output is correct |
| 2 |
Correct |
50 ms |
125516 KB |
Output is correct |
| 3 |
Correct |
50 ms |
125516 KB |
Output is correct |
| 4 |
Correct |
56 ms |
125724 KB |
Output is correct |
| 5 |
Incorrect |
54 ms |
125716 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
125484 KB |
Output is correct |
| 2 |
Correct |
50 ms |
125508 KB |
Output is correct |
| 3 |
Correct |
52 ms |
125452 KB |
Output is correct |
| 4 |
Correct |
59 ms |
125664 KB |
Output is correct |
| 5 |
Incorrect |
54 ms |
125704 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
