oj.uz

Submission #413389

# Submission time Handle Problem Language Result Execution time Memory
413389 2021-05-28T16:23:58 Z pliam Wall (IOI14_wall) C++14
100 / 100
 1293 ms 85264 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000005
#define INF (int)1e9+5

int st[4*MAXN],lazy_lower[4*MAXN],lazy_upper[4*MAXN];//minimum segment tree
int final[MAXN];
int N;

void update(int from,int to,int low,int up,int v=1,int start=0,int end=N-1){
  if(start==from&&end==to){
    st[v]=max(st[v],low);
    st[v]=min(st[v],up);
    if(low>lazy_upper[v]){
      lazy_upper[v]=lazy_lower[v]=low;
    }else if(up<lazy_lower[v]){
      lazy_lower[v]=lazy_upper[v]=up;
    }else{
      lazy_lower[v]=max(lazy_lower[v],low);
      lazy_upper[v]=min(lazy_upper[v],up);
    }
    return;
  }
  int mid=(start+end)/2;
  //propagate
  update(start,mid,lazy_lower[v],lazy_upper[v],2*v,start,mid);
  update(mid+1,end,lazy_lower[v],lazy_upper[v],2*v+1,mid+1,end);
  lazy_lower[v]=0;
  lazy_upper[v]=INF;

  if(to<=mid){
    update(from,to,low,up,2*v,start,mid);
  }else if(from>mid){
    update(from,to,low,up,2*v+1,mid+1,end);
  }else{
    update(from,mid,low,up,2*v,start,mid);
    update(mid+1,to,low,up,2*v+1,mid+1,end);
  }
  st[v]=min(st[2*v],st[2*v+1]);
}

void build(int v=1,int start=0,int end=N-1){
  if(start==end){
    lazy_upper[v]=INF;
    return;
  }
  int mid=(start+end)/2;
  build(2*v,start,mid);
  build(2*v+1,mid+1,end);
  lazy_upper[v]=INF;
}

void build_result(int v=1,int start=0,int end=N-1){
  if(start==end){
    final[start]=st[v];
    return;
  }
  int mid=(start+end)/2;
  //propagate
  update(start,mid,lazy_lower[v],lazy_upper[v],2*v,start,mid);
  update(mid+1,end,lazy_lower[v],lazy_upper[v],2*v+1,mid+1,end);
  lazy_lower[v]=0;
  lazy_upper[v]=INF;

  build_result(2*v,start,mid);
  build_result(2*v+1,mid+1,end);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N=n;
  build();
  for(int i=0;i<k;i++){
    if(op[i]==1){
      update(left[i],right[i],height[i],INF);
    }else{
      update(left[i],right[i],0,height[i]);
    }
  }
  build_result();
  for(int i=0;i<n;i++){
    finalHeight[i]=final[i];
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 9 ms 1100 KB Output is correct
5 Correct 8 ms 1012 KB Output is correct
6 Correct 8 ms 904 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 207 ms 10004 KB Output is correct
3 Correct 268 ms 6436 KB Output is correct
4 Correct 894 ms 14140 KB Output is correct
5 Correct 490 ms 14580 KB Output is correct
6 Correct 531 ms 14672 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 360 KB Output is correct
4 Correct 9 ms 944 KB Output is correct
5 Correct 9 ms 952 KB Output is correct
6 Correct 8 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 154 ms 10060 KB Output is correct
9 Correct 269 ms 6516 KB Output is correct
10 Correct 881 ms 14076 KB Output is correct
11 Correct 506 ms 14640 KB Output is correct
12 Correct 471 ms 14556 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 174 ms 10020 KB Output is correct
15 Correct 48 ms 2260 KB Output is correct
16 Correct 888 ms 14296 KB Output is correct
17 Correct 467 ms 14416 KB Output is correct
18 Correct 464 ms 14352 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 10 ms 972 KB Output is correct
5 Correct 9 ms 972 KB Output is correct
6 Correct 8 ms 992 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 153 ms 10060 KB Output is correct
9 Correct 300 ms 6408 KB Output is correct
10 Correct 772 ms 14044 KB Output is correct
11 Correct 488 ms 14552 KB Output is correct
12 Correct 475 ms 14612 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 160 ms 9968 KB Output is correct
15 Correct 47 ms 2296 KB Output is correct
16 Correct 968 ms 14300 KB Output is correct
17 Correct 480 ms 14404 KB Output is correct
18 Correct 548 ms 14328 KB Output is correct
19 Correct 1233 ms 85236 KB Output is correct
20 Correct 1245 ms 82716 KB Output is correct
21 Correct 1227 ms 85264 KB Output is correct
22 Correct 1273 ms 82732 KB Output is correct
23 Correct 1223 ms 82780 KB Output is correct
24 Correct 1269 ms 82704 KB Output is correct
25 Correct 1223 ms 82668 KB Output is correct
26 Correct 1211 ms 85160 KB Output is correct
27 Correct 1293 ms 85216 KB Output is correct
28 Correct 1202 ms 82664 KB Output is correct
29 Correct 1254 ms 82752 KB Output is correct
30 Correct 1221 ms 82688 KB Output is correct