| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 349452 | David_M | Wall (IOI14_wall) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "wall.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF=1e9+2021;
struct uwu{int type, height, time; uwu (int x, int y, int z){time=x;type=y;height=z;} };
vector<uwu> v[1<<20];
int T[2][1<<23], M[2], K;
void build (int x=1, int l=0, int r=K){
if(l==r){ T[1][x]=(!!l)*INF; return; }
build(x<<1, l, l+r>>1);
build(x<<1|1, l+r+2>>1, r);
T[1][x]=min(T[1][x<<1], T[1][x<<1|1]);
}
void upd(uwu a, int x=1, int l=0, int r=K){
if(l==r){ cout<<a.type<<" "<<a.time<<" "<<x<<" "<<a.height<<endl; T[a.type][x]=a.height; return; }
int mid=l+r>>1;
if(a.time<=mid) upd(a, x<<1, l, mid);
else upd(a, x<<1|1, mid+1, r);
T[0][x]=max(T[0][x<<1], T[0][x<<1|1]);
T[1][x]=min(T[1][x<<1], T[1][x<<1|1]);
}
int get(int x=1, int l=0, int r=K){
if(l==r){
cout<<l<<" "<<M[0]<<" "<<M[1]<<" "<<T[0][x]<<" "<<T[1][x]<<" "<<x<<endl;
M[0]=max(M[0], T[0][x]),
M[1]=min(M[1], T[1][x]);
return (T[0][x]==M[0])?M[1]:M[0];
// if(T[0][x]==M[0])return M[1];
// if(T[1][x]==M[1])return M[0];
// assert(0);
}
int m[]={max(M[0], T[0][x<<1|1]), min(M[1], T[1][x<<1|1])}, mid=l+r>>1;
if(m[1]>m[0]){ M[0]=m[0]; M[1]=m[1]; return get(x<<1, l, mid); }
else return get(x<<1|1, mid+1, r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
K=k; build();
for(int i=0; i<k; i++){
op[i]--;
v[left[i]].pb({i+1, op[i], height[i]});
v[right[i]+1].pb({i+1, op[i], op[i]*INF});
}
// for (int i=1; i<=4*k+2; i++){
// cout<<T[0][i]<<" "<<T[1][i]<<'\n';
// }
for (int i=0; i<n; i++){
for (int j=0; j<v[i].size(); j++) upd(v[i][j]);
M[0]=0; M[1]=INF; finalHeight[i]=get();
}
}
int n, k, op[10], Left[10], Right[10], height[10], finalHeight[10];
main(){
cin>>n>>k;
for (int i=0; i<k; i++){
cin>>op[i]>>Left[i]>>Right[i]>>height[i];
}
buildWall(n, k, op, Left, Right, height, finalHeight);
for (int i=0; i<n; i++){
cout<<finalHeight[i]<<" ";
}
}