oj.uz

Submission #117444

# Submission time Handle Problem Language Result Execution time Memory
117444 2019-06-15T23:46:35 Z dragonslayerit Wall (IOI14_wall) C++14
61 / 100
 682 ms 66268 KB 
#include "wall.h"
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>

//clamps to [a,b]
struct Node{
  int a,b;
  Node():a(INT_MIN),b(INT_MAX){
  }
  Node(int a,int b):a(a),b(b){
    assert(a<=b);
  }
  int eval(int x){
    return std::max(a,std::min(b,x));
  }
};

//apply l, then r
struct Node combine(struct Node l,struct Node r){
  if(l.b<r.a) return Node(r.a,r.a);
  if(l.a>r.b) return Node(r.b,r.b);
  return Node(std::max(l.a,r.a),std::min(l.b,r.b));
}

struct Node st[1000005];
struct Node alt[500005];
std::vector<int> delta[500005];
int K;

void pull(int i){
  st[i]=combine(st[i<<1],st[i<<1|1]);
}

void update(int i){
  for(i+=K;i>1;i>>=1){
    pull(i>>1);
  }
}

struct Node query(int a,int b){
  struct Node lsum,rsum;
  for(a+=K,b+=K;a<b;a>>=1,b>>=1){
    if(a&1) lsum=combine(lsum,st[a++]);
    if(b&1) rsum=combine(st[--b],rsum);
  }
  return combine(lsum,rsum);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  K=k;
  for(int i=0;i<k;i++){
    if(op[i]==1){
      alt[i]=Node(height[i],INT_MAX);
    }else{
      alt[i]=Node(INT_MIN,height[i]);
    }
    delta[left[i]].push_back(i);
    delta[right[i]+1].push_back(i);
  }
  for(int i=0;i<n;i++){
    for(int x:delta[i]){
      std::swap(st[x+K],alt[x]);
      update(x);
    }
    finalHeight[i]=query(0,K).eval(0);
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 25 ms 24184 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 25 ms 24192 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 201 ms 35824 KB Output is correct
3 Correct 181 ms 33272 KB Output is correct
4 Correct 625 ms 43496 KB Output is correct
5 Correct 291 ms 43128 KB Output is correct
6 Correct 277 ms 42764 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 22 ms 24064 KB Output is correct
4 Correct 27 ms 24312 KB Output is correct
5 Correct 29 ms 24184 KB Output is correct
6 Correct 32 ms 24184 KB Output is correct
7 Correct 27 ms 23804 KB Output is correct
8 Correct 210 ms 39004 KB Output is correct
9 Correct 197 ms 33400 KB Output is correct
10 Correct 590 ms 43600 KB Output is correct
11 Correct 286 ms 43032 KB Output is correct
12 Correct 282 ms 42744 KB Output is correct
13 Correct 20 ms 23808 KB Output is correct
14 Correct 225 ms 39016 KB Output is correct
15 Correct 49 ms 25720 KB Output is correct
16 Correct 649 ms 43852 KB Output is correct
17 Correct 312 ms 42632 KB Output is correct
18 Correct 304 ms 42232 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 23 ms 23928 KB Output is correct
4 Correct 26 ms 24244 KB Output is correct
5 Correct 25 ms 24312 KB Output is correct
6 Correct 25 ms 24192 KB Output is correct
7 Correct 21 ms 23808 KB Output is correct
8 Correct 207 ms 38932 KB Output is correct
9 Correct 248 ms 33528 KB Output is correct
10 Correct 584 ms 43384 KB Output is correct
11 Correct 281 ms 42904 KB Output is correct
12 Correct 271 ms 42616 KB Output is correct
13 Correct 20 ms 23808 KB Output is correct
14 Correct 234 ms 39004 KB Output is correct
15 Correct 47 ms 25596 KB Output is correct
16 Correct 682 ms 43768 KB Output is correct
17 Correct 309 ms 42488 KB Output is correct
18 Correct 313 ms 42360 KB Output is correct
19 Runtime error 215 ms 66268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -