oj.uz

Submission #226441

# Submission time Handle Problem Language Result Execution time Memory
226441 2020-04-23T19:42:45 Z a_player Wall (IOI14_wall) C++14
100 / 100
 899 ms 59256 KB 
#include "wall.h"
#ifdef ALE
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define lo first
#define hi second

const int nax=2e6+6;
const int inf=INT_MAX;

pair<int,int> rt[3*nax];

void merge(pair<int,int> a, pair<int,int>& b){
  int oldhi=b.hi;
  b.lo=max(a.lo,b.lo);
  b.hi=min(a.hi,b.hi);
  if(oldhi<a.lo)b.hi=b.lo;
  else if(a.hi<b.lo)b.lo=b.hi;
}

void pre(int k, int x, int y){
  if(x!=y){
      merge(rt[k],rt[2*k]);
      merge(rt[k],rt[2*k+1]);
      rt[k]={0,inf};
  }
}

void update(int k, int a, int b, int x, int y, int mval,int Mval){
  pre(k,x,y);
  if(x>b||y<a)return;
  if(x>=a&&y<=b){
    merge({mval,Mval},rt[k]);
    return;
  }
  int m=(x+y)/2;
  update(2*k,a,b,x,m,mval,Mval);
  update(2*k+1,a,b,m+1,y,mval,Mval);
}
void solve(int k, int x, int y, int* f){
  pre(k,x,y);
  if(x>y)return;
  if(x==y){
    f[x]=rt[k].lo;
    return;
  }
  int m=(x+y)/2;
  solve(2*k,x,m,f);
  solve(2*k+1,m+1,y,f);

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<3*nax;i++)rt[k]={0,inf};
      for(int i=0;i<k;i++){
        if(op[i]==1)update(1,left[i],right[i],0,n-1,height[i],inf);
        else update(1,left[i],right[i],0,n-1,0,height[i]);
      }
      solve(1,0,n-1,finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 768 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 10 ms 768 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 166 ms 8188 KB Output is correct
3 Correct 204 ms 4180 KB Output is correct
4 Correct 540 ms 10872 KB Output is correct
5 Correct 358 ms 11512 KB Output is correct
6 Correct 346 ms 11384 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 11 ms 768 KB Output is correct
5 Correct 9 ms 768 KB Output is correct
6 Correct 10 ms 768 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 168 ms 8184 KB Output is correct
9 Correct 200 ms 4216 KB Output is correct
10 Correct 534 ms 10872 KB Output is correct
11 Correct 356 ms 11512 KB Output is correct
12 Correct 338 ms 11384 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 177 ms 8312 KB Output is correct
15 Correct 45 ms 1400 KB Output is correct
16 Correct 747 ms 11128 KB Output is correct
17 Correct 352 ms 11132 KB Output is correct
18 Correct 361 ms 11128 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 768 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 10 ms 768 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 167 ms 8184 KB Output is correct
9 Correct 208 ms 4216 KB Output is correct
10 Correct 530 ms 10872 KB Output is correct
11 Correct 350 ms 11512 KB Output is correct
12 Correct 340 ms 11512 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 175 ms 8184 KB Output is correct
15 Correct 46 ms 1528 KB Output is correct
16 Correct 721 ms 11132 KB Output is correct
17 Correct 354 ms 11128 KB Output is correct
18 Correct 367 ms 11116 KB Output is correct
19 Correct 822 ms 59204 KB Output is correct
20 Correct 829 ms 56640 KB Output is correct
21 Correct 832 ms 59256 KB Output is correct
22 Correct 863 ms 56568 KB Output is correct
23 Correct 856 ms 56696 KB Output is correct
24 Correct 899 ms 56568 KB Output is correct
25 Correct 848 ms 56824 KB Output is correct
26 Correct 832 ms 59256 KB Output is correct
27 Correct 846 ms 59256 KB Output is correct
28 Correct 833 ms 56668 KB Output is correct
29 Correct 822 ms 56812 KB Output is correct
30 Correct 848 ms 56844 KB Output is correct