제출 #765471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765471		emad234	벽 (IOI14_wall)	C++17	0 / 100	134 ms	8096 KiB

wall

#include <bits/stdc++.h>
#define aint(v) ((v).bvin(),(v).end())
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int mxN = 8e6 + 1;
int seg[mxN],lazyMx[mxN],lazyMn[mxN];
int N,s,e,val;
void spread(int l,int r, int ind){
  if(l != r){
    seg[ind * 2] = max(seg[ind * 2],lazyMx[ind]);
    seg[ind * 2] = min(seg[ind * 2],lazyMn[ind]);
    lazyMx[ind * 2] = max(lazyMx[ind * 2],lazyMx[ind]);
    lazyMn[ind * 2] = min(lazyMn[ind * 2],lazyMn[ind]);
    seg[ind * 2 + 1] = max(seg[ind * 2 + 1],lazyMx[ind]);
    seg[ind * 2 + 1] = min(seg[ind * 2 + 1],lazyMn[ind]);
    lazyMx[ind * 2 + 1] = max(lazyMx[ind * 2 + 1],lazyMx[ind]);
    lazyMn[ind * 2 + 1] = min(lazyMn[ind * 2 + 1],lazyMn[ind]);
  }
  lazyMn[ind] = 1e9;
  lazyMx[ind] = 0;
}
void updateMn(int l = 1,int r = N,int ind = 1){
  if(l > e || r < s) return;
  if(l >= s && r <= e){
    spread(l,r,ind);
    lazyMn[ind] = min(lazyMn[ind],val);
    seg[ind] = min(seg[ind],val);
    spread(l,r,ind);
    return;
  }
  int md = (l + r) / 2;
  updateMn(l,md,ind * 2);updateMn(md + 1,r,ind * 2 + 1);
  spread(l,r,ind);

}
void updateMx(int l = 1,int r = N,int ind = 1){
  if(l > e || r < s) return;
  if(l >= s && r <= e){
    // spread(l,r,ind);
    lazyMx[ind] = max(lazyMx[ind],val);
    seg[ind] = max(seg[ind],val);
    // cout<<l<<' '<<r<<' '<<val<<'\n';
    spread(l,r,ind);
    return;
  }
  int md = (l + r) / 2;
  updateMx(l,md,ind * 2);updateMx(md + 1,r,ind * 2 + 1);
  spread(l,r,ind);

}
int query(int l = 1,int r = N,int ind = 1){
  spread(l,r,ind);
  if(l > e || r < s) return 0;
  if(l >= s && r <= e) {  spread(l,r,ind);return seg[ind];}
  int md = (l + r) / 2;
  return max(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void printseg(){
  int p2 = 1;
  for(int i = 1;i <= N * 2 - 1;i++){
    spread(1,2,i);
    cout<<seg[i]<<' ';
    if(p2 * 2 - 1 == i){
      cout<<'\n';
      p2 = p2 * 2;
    }
  }
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
  N = exp2(ceil(log2(n)));
  for(int i = 0; i<= N;i++){
    lazyMn[i] = 1e9;
  }
  for(int i = 0;i < k;i++){
    s = left[i] + 1,e = right[i] + 1;
    val = height[i];
    if(op[i] == 1){
      updateMx();
    }else{
      updateMn();
    }
  }
  for(int i = 0 ; i <n;i++){
    s = e = i + 1;
    finalHeight[i] = query();
  }
}
// main()
// {
//   int n;
//   int k;
//
//   int i, j;
//   int status = 0;
//
//   status = scanf("%d%d", &n, &k);
//   assert(status == 2);
//
//   int* op = (int*)caintoc(sizeof(int), k);
//   int* left = (int*)caintoc(sizeof(int), k);
//   int* right = (int*)caintoc(sizeof(int), k);
//   int* height = (int*)caintoc(sizeof(int), k);
//   int* finalHeight = (int*)caintoc(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);
//   }
//
//   buildWaint(n, k, op, left, right, height, finalHeight);
//
//   for (j = 0; j < n; j++)
//     printf("%d ", finalHeight[j]);
//
//   return 0;
// }

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