oj.uz

답안 #1013836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013836 2024-07-04T06:44:54 Z amirhoseinfar1385 벽 (IOI14_wall) C++17
100 / 100
 827 ms 86120 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000+10,lg=21,kaf=(1<<lg);
int inf=1e9+5;

struct segment{
  struct node{
    int l,r,now;
    node(){
      now=l=0;
      r=inf;
    }
  };
  node seg[(1<<(lg+1))];
  void calc(int i){
    if(i>=kaf){
      //cout<<i-kaf<<" "<<seg[i].now<<" "<<seg[i].l<<" "<<seg[i].r<<endl;
      seg[i].now=max(seg[i].now,seg[i].l);
      seg[i].now=min(seg[i].now,seg[i].r);
      seg[i].l=0;
      seg[i].r=inf;
      return ;
    }
  }
  void shift(int i){
    if(i>=kaf){
      return calc(i);
    }
    seg[(i<<1)].l=max(seg[i].l,seg[(i<<1)].l);
    seg[(i<<1)^1].l=max(seg[i].l,seg[(i<<1)^1].l);
    seg[(i<<1)].r=min(seg[(i<<1)].r,seg[i].r);
    seg[(i<<1)^1].r=min(seg[i].r,seg[(i<<1)^1].r);
    if(seg[(i<<1)].l>seg[(i<<1)].r){
      if(seg[i].l==seg[(i<<1)].l){
        seg[(i<<1)].r=seg[i].l;
      }else{
        seg[(i<<1)].l=seg[i].r;
      }
    }
    if(seg[(i<<1)^1].l>seg[(i<<1)^1].r){
      if(seg[i].l==seg[(i<<1)^1].l){
        seg[(i<<1)^1].r=seg[i].l;
      }else{
        seg[(i<<1)^1].l=seg[i].r;
      }
    }
    seg[i].l=0;
    seg[i].r=inf;
    return ;
  }
  void upd(int i,int l,int r,int tl,int tr,int vas,int w){
    if(l>r||l>tr||r<tl||tl>tr){
      return ;
    }
    shift(i);
    if(l>=tl&&r<=tr){
      if(vas==1){
        seg[i].l=max(seg[i].l,w);
      }else{
        seg[i].r=min(seg[i].r,w);
      }
      ////cout<<"upd: "<<l<<" "<<r<<" "<<vas<<" "<<w<<" "<<seg[i].l<<endl;
      shift(i);
      calc(i);
      //if(l==4&&r==5)
      ////cout<<"upd: "<<l<<" "<<r<<" "<<vas<<" "<<w<<" "<<seg[(i<<1)^1].l<<endl;
      return ;
    }
    int m=(l+r)>>1;
    upd((i<<1),l,m,tl,tr,vas,w);
    upd((i<<1)^1,m+1,r,tl,tr,vas,w);
    calc(i);
    return ;
  }
  int pors(int i,int l,int r,int tl,int tr){
    if(l>r||l>tr||r<tl||tl>tr){
      return 0;
    }
    shift(i);
    calc(i);
    if(l>=tl&&r<=tr){
      return seg[i].now;
    }
    int m=(l+r)>>1;
    return pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);;
  }
}seg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<k;i++){
    seg.upd(1,0,kaf-1,left[i],right[i],op[i],height[i]);
  }
  for(int i=0;i<n;i++){
    finalHeight[i]=seg.pors(1,0,kaf-1,i,i);
  }
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 49496 KB Output is correct
2 Correct 21 ms 49752 KB Output is correct
3 Correct 19 ms 49604 KB Output is correct
4 Correct 26 ms 49872 KB Output is correct
5 Correct 23 ms 49756 KB Output is correct
6 Correct 24 ms 49872 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 49496 KB Output is correct
2 Correct 195 ms 63136 KB Output is correct
3 Correct 170 ms 56660 KB Output is correct
4 Correct 427 ms 67668 KB Output is correct
5 Correct 259 ms 68688 KB Output is correct
6 Correct 244 ms 67124 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 49500 KB Output is correct
2 Correct 18 ms 49584 KB Output is correct
3 Correct 18 ms 49756 KB Output is correct
4 Correct 24 ms 49756 KB Output is correct
5 Correct 24 ms 49752 KB Output is correct
6 Correct 22 ms 49928 KB Output is correct
7 Correct 17 ms 49644 KB Output is correct
8 Correct 178 ms 63312 KB Output is correct
9 Correct 162 ms 56656 KB Output is correct
10 Correct 432 ms 67624 KB Output is correct
11 Correct 275 ms 68688 KB Output is correct
12 Correct 270 ms 67084 KB Output is correct
13 Correct 19 ms 49496 KB Output is correct
14 Correct 205 ms 63312 KB Output is correct
15 Correct 53 ms 50776 KB Output is correct
16 Correct 588 ms 67924 KB Output is correct
17 Correct 260 ms 67156 KB Output is correct
18 Correct 245 ms 67156 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 49500 KB Output is correct
2 Correct 21 ms 49752 KB Output is correct
3 Correct 20 ms 49756 KB Output is correct
4 Correct 28 ms 49872 KB Output is correct
5 Correct 24 ms 49880 KB Output is correct
6 Correct 30 ms 49828 KB Output is correct
7 Correct 25 ms 49500 KB Output is correct
8 Correct 189 ms 63312 KB Output is correct
9 Correct 164 ms 56656 KB Output is correct
10 Correct 433 ms 67604 KB Output is correct
11 Correct 263 ms 68688 KB Output is correct
12 Correct 253 ms 67156 KB Output is correct
13 Correct 19 ms 49500 KB Output is correct
14 Correct 200 ms 63312 KB Output is correct
15 Correct 53 ms 50700 KB Output is correct
16 Correct 596 ms 67716 KB Output is correct
17 Correct 254 ms 67292 KB Output is correct
18 Correct 263 ms 67272 KB Output is correct
19 Correct 778 ms 86120 KB Output is correct
20 Correct 787 ms 83556 KB Output is correct
21 Correct 783 ms 85868 KB Output is correct
22 Correct 747 ms 83568 KB Output is correct
23 Correct 730 ms 83452 KB Output is correct
24 Correct 808 ms 83520 KB Output is correct
25 Correct 827 ms 83400 KB Output is correct
26 Correct 813 ms 85840 KB Output is correct
27 Correct 806 ms 85860 KB Output is correct
28 Correct 790 ms 83428 KB Output is correct
29 Correct 795 ms 83480 KB Output is correct
30 Correct 814 ms 83336 KB Output is correct