| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 423439 |
2021-06-11T06:26:30 Z |
ismoilov |
Wall (IOI14_wall) |
C++14 |
|
11 ms |
17612 KB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define maxx 2222222
#define inf 1e9
int mx[4*maxx], mn[4*maxx];
bool vis[maxx*4];
void maximize(int, int, int, int, int, int);
void minimize(int, int, int, int, int, int);
void max_self(int &a, int b){
if(b > a)
a = b;
}
void min_self(int &a, int b){
if(b < a)
a = b;
}
void minimize(int v, int l, int r, int tl, int tr, int h){
if(tr < l || tl > r)
return;
if(tr >= r && tl <= l){
min_self(mn[v], h);
max_self(mx[v], mn[v]);
vis[v] = 1;
return;
}
int m = (l + r) >> 1;
if(vis[v]){
vis[v] = 0;
vis[v+v] = vis[v+v+1] = 1;
maximize(v+v, l, m, l, m, mx[v]);
minimize(v+v, l, m, l, m, mn[v]);
maximize(v+v+1, m+1, r, m+1, r, mx[v]);
minimize(v+v+1, m+1, r, m+1, r, mn[v]);
mx[v] = 0;
mn[v] = inf;
}
minimize(v+v, l, m, tl, tr, h);
minimize(v+v+1, m+1, r, tl, tr, h);
}
void maximize(int v, int l, int r, int tl, int tr, int h){
if(tr < l || tl > r)
return;
if(tl <= l && tr >= r){
max_self(mx[v], h);
max_self(mn[v], mx[v]);
vis[v] = 1;
return;
}
int m = (l + r) >> 1;
if(vis[v]){
vis[v] = 0;
vis[v+v] = vis[v+v+1] = 1;
maximize(v+v, l, m, l, m, mx[v]);
minimize(v+v, l, m, l, m, mn[v]);
maximize(v+v+1, m+1, r, m+1, r, mx[v]);
minimize(v+v+1, m+1, r, m+1, r, mn[v]);
mx[v] = 0;
mn[v] = inf;
}
maximize(v+v, l, m, tl, tr, h);
maximize(v+v+1, m+1, r, tl, tr, h);
}
int get(int pos, int tl, int tr, int x){
if(tl == tr)
return mx[pos];
int m = (tl+tr) >> 1;
if(x <= m)
return get(pos+pos, tl, m, x);
else
return get(pos+pos+1, m+1, tr, x);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fp(i,0,maxx){
mx[i] = 0;
mn[i] = inf;
}
fp(i,0,k){
if(op[i] == 1)
maximize(1, 1, n, left[i]+1, right[i]+1, height[i]);
else
minimize(1, 1, n, left[i]+1, right[i]+1, height[i]);
}
fpp(i,1,n){
minimize(1, 1, n, i, i, inf);
finalHeight[i-1] = get(1, 1, n, i);
}
return;
}
Compilation message
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
7 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
| ^
wall.cpp:90:2: note: in expansion of macro 'fp'
90 | fp(i,0,maxx){
| ^~
wall.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
7 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
| ^
wall.cpp:95:2: note: in expansion of macro 'fp'
95 | fp(i,0,k){
| ^~
wall.cpp:8:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
8 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
| ^
wall.cpp:102:2: note: in expansion of macro 'fpp'
102 | fpp(i,1,n){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
17612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
17612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
17612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
17612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
