| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 235972 |
2020-05-30T14:10:07 Z |
crossing0ver |
Wall (IOI14_wall) |
C++17 |
|
191 ms |
8056 KB |
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2E6;
int t[4*N][2],lazy[4*N][2],l,r,val;// min h, max h
bool type;
void push(int v,int tl,int tr) {
if (lazy[v][0]) {
if (lazy[v*2][0] < lazy[v][0] || !t[v*2][0])
lazy[v*2][0] = t[v*2][0] = lazy[v][0]; //lazy[v*2][1] = max(lazy[v*2][1],lazy[v][0]), t[v*2][1] = max (t[v*2][1],[lazy[v][0]]);
if (lazy[v*2|1][0] < lazy[v][0] || !t[v*2|1][0])
lazy[v*2|1][0] = t[v*2|1][0] = lazy[v][0] ; //lazy[v*2|1][1] = max(t[v*2|1][1],lazy[v][0]), t[v*2|1][1] = max (t[v*2|1][1],[lazy[v][0]]);
lazy[v][0] = 0;
if (t[v*2][0] > t[v*2][1] || !t[v*2][1]) {
t[v*2][1] = lazy[v*2][1] = lazy[v*2][0]; }
if (t[v*2|1][0] > t[v*2|1][1] || !t[v*2|1][1]) {
t[v*2|1][1] = lazy[v*2|1][1] = lazy[v*2|1][0]; }
}
if (lazy[v][1]) {
if (lazy[v*2][1] > lazy[v][1] || !t[v*2][1])
lazy[v*2][1] = t[v*2][1] = lazy[v][1];
if (lazy[v*2|1][1] > lazy[v][1] != t[v*2|1][1])
lazy[v*2|1][1] = t[v*2|1][1] = lazy[v][1];
if (t[v*2][0] > t[v*2][1] || !t[v*2][0]){
t[v*2][0] = lazy[v*2][0] = lazy[v*2][1]; }
if (t[v*2|1][0] > lazy[v*2|1][1] || !t[v*2|1][0]) {
t[v*2|1][0] = lazy[v*2|1][0] = lazy[v*2|1][1];
}
lazy[v][1] = 0;
}
}
void upd (int v,int tl,int tr) {
if (l > tr || r < tl) return;
if (tl >= l && tr <= r) {
if (type == 0) {
if (t[v][0] >= val) return;
t[v][0] = max (t[v][0],val);
lazy[v][0] = max (lazy[v][0],val);
if (t[v][1] < val) {
t[v][1] = lazy[v][1] = val;
}
}
else {
if (t[v][1] <= val && t[v][1]) return;
t[v][1] = val;
lazy[v][1] = val;
if (t[v][0] > val) {
t[v][0] = lazy[v][0] = val;
}
}
return;
}
push (v,tl,tr);
int tm = (tl + tr)/2;
upd (v*2,tl,tm);
upd (v*2|1,tm+1,tr);
if (t[v*2][0] && t[v*2|1][0])
t[v][0] = min(t[v*2][0],t[v*2|1][0]);
else t[v][0] = max(t[v*2][0],t[v*2|1][0]);
t[v][1] = max(t[v*2][1],t[v*2|1][1]);
}
int A[N];
void get (int v,int tl,int tr) {
if (tl == tr) A[tl] = t[v][0];
else {
int tm = (tl + tr)/2;
push(v,tl,tr);
get(v*2,tl,tm);
get(v*2+1,tm+1,tr);
}
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]) {
for (int i = 0; i < k; i++) {
type = op[i] - 1;
l = left[i];
r = right[i];
val = height[i] + 1;
upd (1,0,n-1);
}
get(1,0,n-1);
for (int i = 0;i < n; i++)
finalHeight[i] = max (A[i] - 1,0);
}
Compilation message
wall.cpp: In function 'void push(int, int, int)':
wall.cpp:23:22: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
if (lazy[v*2|1][1] > lazy[v][1] != t[v*2|1][1])
~~~~~~~~~~~~~~~^~~~~~~~~~~~
wall.cpp:23:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (lazy[v*2|1][1] > lazy[v][1] != t[v*2|1][1])
^~
wall.cpp:25:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if (t[v*2][0] > t[v*2][1] || !t[v*2][0]){
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
181 ms |
8056 KB |
Output is correct |
| 3 |
Incorrect |
191 ms |
4856 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
