| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 881202 |
2023-11-30T21:22:01 Z |
MarwenElarbi |
Wall (IOI14_wall) |
C++17 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "wall.h"
using namespace std;
const int nax = 2e6+5;
const int inf=(1<<31);
int lazy[nax*4][2];
int segtree[nax*4][2];
int tab[nax];
void expand(int pos){
if(lazy[pos][0]!=-inf){
segtree[pos*2+1][0]=max(segtree[pos*2+1][0],lazy[pos][0]);
segtree[pos*2+2][0]=max(segtree[pos*2+2][0],lazy[pos][0]);
segtree[pos*2+1][1]=max(segtree[pos*2+1][1],lazy[pos][0]);
segtree[pos*2+2][1]=max(segtree[pos*2+2][1],lazy[pos][0]);
lazy[pos*2+1][0]=max(lazy[pos*2+1][0],lazy[pos][0]);
lazy[pos*2+2][0]=max(lazy[pos*2+2][0],lazy[pos][0]);
//lazy[pos*2+1][1]=max(lazy[pos*2+1][1],lazy[pos][0]);
//lazy[pos*2+2][1]=max(lazy[pos*2+2][1],lazy[pos][0]);
}
if(lazy[pos][1]!=inf){
segtree[pos*2+1][0]=min(segtree[pos*2+1][0],lazy[pos][1]);
segtree[pos*2+2][0]=min(segtree[pos*2+2][0],lazy[pos][1]);
segtree[pos*2+1][1]=min(segtree[pos*2+1][1],lazy[pos][1]);
segtree[pos*2+2][1]=min(segtree[pos*2+2][1],lazy[pos][1]);
lazy[pos*2+1][1]=lazy[pos*2+2][1]=inf;
lazy[pos*2+1][1]=min(lazy[pos*2+1][1],lazy[pos][1]);
lazy[pos*2+2][1]=min(lazy[pos*2+2][1],lazy[pos][1]);
//lazy[pos*2+1][0]=min(lazy[pos*2+1][0],lazy[pos][1]);
//lazy[pos*2+2][0]=min(lazy[pos*2+2][0],lazy[pos][1]);
}
lazy[pos][0]=inf;
lazy[pos][1]=-inf;
return;
}
void update(int pos,int l,int r,int left,int right,int value,int type){
if(l>r||l>right||r<left) return;
if(l>=left&&r<=right){
//expand(pos);
if(type==1){
if (segtree[pos][0]<value) lazy[pos][0]=value;
segtree[pos][0]=max(segtree[pos][0],value);
segtree[pos][1]=max(segtree[pos][1],value);
//lazy[pos][1]=max(lazy[pos][1],value);
}else{
if (segtree[pos][1]>value) lazy[pos][1]=value;
segtree[pos][1]=min(segtree[pos][1],value);
segtree[pos][0]=min(segtree[pos][0],value);
//lazy[pos][0]=min(segtree[pos][0],value);
//cout <<l<<" "<<r<<" "<<segtree[pos][1]<<endl;
}
return;
}
//cout <<l<<" "<<r<<" "<<lazy[pos][0]<<" "<<lazy[pos][1]<<endl;
expand(pos);
int mid=(r+l)/2;
update(pos*2+1,l,mid,left,right,value,type);
update(pos*2+2,mid+1,r,left,right,value,type);
segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
//cout << l<<" "<<r<<" "<<segtree[pos][0]<<" "<<segtree[pos][1]<<endl;
//cout <<l<<" "<<r<<" "<<segtree[pos][1]<<endl;
}
void build(int pos,int l,int r){
if(l==r){
tab[l]=segtree[pos][0];
return;
}
expand(pos);
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < nax*4; ++i)
{
lazy[i][0]=inf;
lazy[i][1]=-inf;
}
for(int i=0;i<k;i++){
if(op[i]==1){
int l=left[i];
int r=right[i];
int x=height[i];
update(0,0,n-1,l,r,x,1);
}else{
int l=left[i];
int r=right[i];
int x=height[i];
update(0,0,n-1,l,r,x,2);
}//cout <<endl;
}//cout <<endl;
build(0,0,n-1);
for (int i = 0; i < n; ++i)
{
finalHeight[i]=tab[i];
}
return;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
int k;
int i, j;
int status = 0;
status = scanf("%d%d", &n, &k);
assert(status == 2);
int* op = (int*)calloc(sizeof(int), k);
int* left = (int*)calloc(sizeof(int), k);
int* right = (int*)calloc(sizeof(int), k);
int* height = (int*)calloc(sizeof(int), k);
int* finalHeight = (int*)calloc(sizeof(int), n);
for (i = 0; i < k; i++){
status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
assert(status == 4);
}
buildWall(n, k, op, left, right, height, finalHeight);
for (j = 0; j < n; j++)
printf("%d\n", finalHeight[j]);
return 0;
}
Compilation message
wall.cpp: In function 'void expand(int)':
wall.cpp:14:22: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
14 | if(lazy[pos][0]!=-inf){
| ^~~~
wall.cpp:36:18: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
36 | lazy[pos][1]=-inf;
| ^~~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:85:20: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
85 | lazy[i][1]=-inf;
| ^~~~
wall.cpp: In function 'int main()':
wall.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccqmHdcR.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccc02jhR.o:wall.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
