oj.uz

Submission #226440

# Submission time Handle Problem Language Result Execution time Memory
226440 2020-04-23T19:41:56 Z a_player Wall (IOI14_wall) C++14
61 / 100
 739 ms 16504 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[2*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 4 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 11 ms 896 KB Output is correct
5 Correct 9 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 170 ms 8176 KB Output is correct
3 Correct 201 ms 4216 KB Output is correct
4 Correct 534 ms 10808 KB Output is correct
5 Correct 356 ms 11296 KB Output is correct
6 Correct 339 ms 11384 KB Output is correct

Subtask #3
29.0 / 29.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 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 166 ms 8184 KB Output is correct
9 Correct 192 ms 4216 KB Output is correct
10 Correct 534 ms 10872 KB Output is correct
11 Correct 374 ms 11384 KB Output is correct
12 Correct 345 ms 11384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 173 ms 8120 KB Output is correct
15 Correct 45 ms 1400 KB Output is correct
16 Correct 721 ms 11128 KB Output is correct
17 Correct 353 ms 11128 KB Output is correct
18 Correct 366 ms 11128 KB Output is correct

Subtask #4
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 11 ms 768 KB Output is correct
6 Correct 11 ms 768 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 165 ms 8312 KB Output is correct
9 Correct 192 ms 4316 KB Output is correct
10 Correct 534 ms 10956 KB Output is correct
11 Correct 358 ms 11464 KB Output is correct
12 Correct 350 ms 11384 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 174 ms 8184 KB Output is correct
15 Correct 43 ms 1528 KB Output is correct
16 Correct 739 ms 11128 KB Output is correct
17 Correct 355 ms 11128 KB Output is correct
18 Correct 354 ms 11168 KB Output is correct
19 Runtime error 209 ms 16504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -