# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
57947 |
2018-07-16T14:24:39 Z |
zetapi |
Wall (IOI14_wall) |
C++14 |
|
0 ms |
0 KB |
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=5e6;
struct data
{
int Min;
int Max;
} Seg[MAX];
void UpdateMin(int low,int high,int node,int qlow,int qhigh,int delta)
{
if(low>high or qlow>qhigh or qhigh<low or qlow>high)
return ;
if(low>=qlow and high<=qhigh)
{
if(Seg[node].Min>delta)
return ;
Seg[node].Min=delta;
Seg[node].Max=max(Seg[node].Max,Seg[node].Min);
return ;
}
int mid=(low+high)/2;
UpdateMin(low,mid,2*node,qlow,qhigh,delta);
UpdateMin(mid+1,high,2*node+1,qlow,qhigh,delta);
Seg[node].Min=max(Seg[node].Min,max(Seg[2*node].Min,Seg[2*node+1].Min));
Seg[node].Max=min(Seg[node].Max,min(Seg[2*node].Max,Seg[2*node+1].Max));
return ;
}
void UpdateMax(int low,int high,int node,int qlow,int qhigh,int delta)
{
if(low>high or qlow>qhigh or qhigh<low or qlow>high)
return ;
if(low>=qlow and high<=qhigh)
{
if(Seg[node].Max<delta)
return ;
Seg[node].Max=delta;
Seg[node].Min=min(Seg[node].Min,Seg[node].Max);
return ;
}
int mid=(low+high)/2;
UpdateMax(low,mid,2*node,qlow,qhigh,delta);
UpdateMax(mid+1,high,2*node+1,qlow,qhigh,delta);
Seg[node].Min=max(Seg[node].Min,max(Seg[2*node].Min,Seg[2*node+1].Min));
Seg[node].Max=min(Seg[node].Max,min(Seg[2*node].Max,Seg[2*node+1].Max));
return ;
}
int query(int low,int high,int node,int X,int CurMin,int CurMax)
{
CurMin=max(CurMin,Seg[node].Min);
CurMax=min(CurMax,Seg[node].Max);
if(low==high)
return CurMin;
int mid=(low+high)/2;
if(X>=low and X<=mid)
return query(low,mid,2*node,X,CurMin,CurMax);
else
return query(mid+1,high,2*node+1,X,CurMin,CurMax);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
int N=n,K=k;
for(int A=0;A<K;A++)
{
if(op[A]==1)
UpdateMin(1,N,1,left[A]+1,right[A]+1,height[A]);
else
UpdateMax(1,N,1,left[A]+1,right[A]+1,height[A]);
}
for(int A=0;A<N;A++)
finalHeight[A]=query(1,N,1,A+1,0,MAX);
return;
}
/*signed main()
{
ios_base::sync_with_stdio(false);
return 0;
}*/
Compilation message
/tmp/ccvzCXqR.o: In function `main':
grader.cpp:(.text.startup+0x113): undefined reference to `buildWall(int, int, int*, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status