oj.uz

Submission #226438

# Submission time Handle Problem Language Result Execution time Memory
226438 2020-04-23T19:38:45 Z a_player Wall (IOI14_wall) C++14
100 / 100
 850 ms 69752 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[4*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<4*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 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 1024 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 170 ms 13944 KB Output is correct
3 Correct 201 ms 8072 KB Output is correct
4 Correct 543 ms 20600 KB Output is correct
5 Correct 366 ms 21496 KB Output is correct
6 Correct 357 ms 20088 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 836 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 172 ms 13944 KB Output is correct
9 Correct 206 ms 8068 KB Output is correct
10 Correct 537 ms 20600 KB Output is correct
11 Correct 356 ms 21496 KB Output is correct
12 Correct 337 ms 19960 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 175 ms 13944 KB Output is correct
15 Correct 46 ms 2040 KB Output is correct
16 Correct 735 ms 20728 KB Output is correct
17 Correct 363 ms 20192 KB Output is correct
18 Correct 355 ms 20088 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 171 ms 14176 KB Output is correct
9 Correct 199 ms 8056 KB Output is correct
10 Correct 528 ms 20528 KB Output is correct
11 Correct 385 ms 21576 KB Output is correct
12 Correct 356 ms 20088 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 178 ms 13944 KB Output is correct
15 Correct 45 ms 2044 KB Output is correct
16 Correct 729 ms 20856 KB Output is correct
17 Correct 362 ms 20088 KB Output is correct
18 Correct 368 ms 20088 KB Output is correct
19 Correct 842 ms 69752 KB Output is correct
20 Correct 850 ms 67096 KB Output is correct
21 Correct 841 ms 69592 KB Output is correct
22 Correct 836 ms 67064 KB Output is correct
23 Correct 827 ms 67252 KB Output is correct
24 Correct 834 ms 67064 KB Output is correct
25 Correct 828 ms 67192 KB Output is correct
26 Correct 828 ms 69624 KB Output is correct
27 Correct 820 ms 69624 KB Output is correct
28 Correct 822 ms 67064 KB Output is correct
29 Correct 814 ms 67224 KB Output is correct
30 Correct 829 ms 67192 KB Output is correct