제출 #1062732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062732		NemanjaSo2005	벽 (IOI14_wall)	C++17	100 / 100	390 ms	166024 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e6+5;
int N,Q,K,tip[maxn],vis[maxn];
vector<int> poc[maxn],kraj[maxn];
struct slog{
   int res=0,minr=1e9;
} st[maxn];
slog spoj(slog a,slog b){
   slog ret;
   ret.minr=min(a.minr,b.minr);
   ret.res=max(b.res,min(a.res,b.minr));
   return ret;
}
void update(int gde,slog sta){
   gde+=K;
   st[gde]=sta;
   gde/=2;
   while(gde){
      st[gde]=spoj(st[gde*2],st[gde*2+1]);
      gde/=2;
   }
   return;
}
void akt(int x){
   slog sta;
   if(tip[x]==1)
      sta.res=vis[x];
   else
      sta.minr=vis[x];
   update(x,sta);
}
void deakt(int x){
   slog a;
   update(x,a);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   N=n;
   Q=k;
   K=1;
   while(K<Q)
      K<<=1;
   for(int i=0;i<Q;i++){
      poc[left[i]].push_back(i);
      kraj[right[i]+1].push_back(i);
      tip[i]=op[i];
      vis[i]=height[i];
   }
   for(int i=0;i<N;i++){
      for(int x:poc[i])
         akt(x);
      for(int x:kraj[i])
         deakt(x);
      finalHeight[i]=st[1].res;
   }
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39