| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 20886 |
2017-03-04T15:53:18 Z |
14kg |
벽 (IOI14_wall) |
C++11 |
|
0 ms |
0 KB |
#include <stdio.h>
#define N 2000001
#define max2(x,y) (x>y?x:y)
#define min2(x,y) (x<y?x:y)
struct WALL{
int op, h;
} Tree[N * 4][2], NONO;
int n, nn, m;
WALL make_WALL(int op, int h){
WALL temp;
temp.op = op, temp.h = h;
return temp;
}
void g(int lev, WALL num){
if (num.op == -1) return;
if (Tree[lev][0].op == -1){ Tree[lev][0] = num; return; }
if (Tree[lev][1].op == -1){ Tree[lev][1] = num; return; }
if (Tree[lev][0].op == Tree[lev][1].op){
if (Tree[lev][0].op == 1) Tree[lev][0].h = max2(Tree[lev][0].h, Tree[lev][1].h);
else Tree[lev][0].h = min2(Tree[lev][0].h, Tree[lev][1].h);
Tree[lev][1] = num; return;
}
if (Tree[lev][1].op == num.op){
if (num.op == 1) Tree[lev][1].h = max2(Tree[lev][1].h, num.h);
else Tree[lev][1].h = min2(Tree[lev][1].h, num.h);
return;
}
if (Tree[lev][1].op == 1){
if (Tree[lev][1].h > Tree[lev][0].h){
if (num.h < Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
return;
}
if (num.h < Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
}
else{
if (Tree[lev][0].h>Tree[lev][1].h){
if (num.h>Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
return;
}
if (num.h > Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
}
}
void Push(int lev, int l, int r, int x, int y, WALL num){
int mid = (l + r) / 2;
if (r < x || y < l) return;
if (x <= l && r <= y){ g(lev, num); return; }
g(lev * 2, Tree[lev][0]), g(lev * 2, Tree[lev][1]);
g(lev * 2 + 1, Tree[lev][0]), g(lev * 2 + 1, Tree[lev][1]);
Tree[lev][0] = Tree[lev][1] = NONO;
Push(lev * 2, l, mid, x, y, num), Push(lev * 2 + 1, mid + 1, r, x, y, num);
}
int get_h(int lev, int h){
if (lev == 0) return h;
if (Tree[lev][0].op == 1) h = max2(h, Tree[lev][0].h);
if (Tree[lev][0].op == 2) h = min2(h, Tree[lev][0].h);
if (Tree[lev][1].op == 1) h = max2(h, Tree[lev][1].h);
if (Tree[lev][1].op == 2) h = min2(h, Tree[lev][1].h);
return get_h(lev / 2, h);
}
int main(){
WALL temp;
int x, y;
scanf("%d %d", &n, &m), NONO = make_WALL(-1, -1);
for (nn = 1; nn < n; nn *= 2);
for (int i = 1; i < nn * 2; i++) Tree[i][0] = Tree[i][1] = NONO;
for (int i = 1; i <= m; i++){
scanf("%d %d %d %d", &temp.op, &x, &y, &temp.h), x++, y++;
Push(1, 1, nn, x, y, temp);
}
for (int i = 1; i <= n; i++) printf("%d\n", get_h(nn + i - 1, 0));
}
Compilation message
wall.cpp: In function 'int main()':
wall.cpp:71:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m), NONO = make_WALL(-1, -1);
^
wall.cpp:76:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &temp.op, &x, &y, &temp.h), x++, y++;
^
/tmp/ccrnAxSx.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cctOMwHt.o:wall.cpp:(.text.startup+0x0): first defined here
/tmp/ccrnAxSx.o: In function `main':
grader.cpp:(.text.startup+0x115): undefined reference to `buildWall(int, int, int*, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status
