oj.uz

Submission #117445

# Submission time Handle Problem Language Result Execution time Memory
117445 2019-06-15T23:49:12 Z dragonslayerit Wall (IOI14_wall) C++14
100 / 100
 728 ms 111224 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[2000005];
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 49 ms 59128 KB Output is correct
2 Correct 50 ms 59128 KB Output is correct
3 Correct 48 ms 59128 KB Output is correct
4 Correct 54 ms 59384 KB Output is correct
5 Correct 53 ms 59384 KB Output is correct
6 Correct 52 ms 59384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 59000 KB Output is correct
2 Correct 228 ms 71132 KB Output is correct
3 Correct 208 ms 65404 KB Output is correct
4 Correct 623 ms 75532 KB Output is correct
5 Correct 315 ms 75224 KB Output is correct
6 Correct 299 ms 74744 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 59000 KB Output is correct
2 Correct 51 ms 59140 KB Output is correct
3 Correct 50 ms 59000 KB Output is correct
4 Correct 53 ms 59384 KB Output is correct
5 Correct 52 ms 59384 KB Output is correct
6 Correct 51 ms 59384 KB Output is correct
7 Correct 48 ms 59060 KB Output is correct
8 Correct 237 ms 71116 KB Output is correct
9 Correct 242 ms 65272 KB Output is correct
10 Correct 661 ms 75640 KB Output is correct
11 Correct 312 ms 75128 KB Output is correct
12 Correct 301 ms 74744 KB Output is correct
13 Correct 48 ms 59000 KB Output is correct
14 Correct 255 ms 70944 KB Output is correct
15 Correct 81 ms 60280 KB Output is correct
16 Correct 728 ms 75936 KB Output is correct
17 Correct 337 ms 74616 KB Output is correct
18 Correct 341 ms 74360 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 59000 KB Output is correct
2 Correct 51 ms 59156 KB Output is correct
3 Correct 49 ms 59132 KB Output is correct
4 Correct 56 ms 59304 KB Output is correct
5 Correct 54 ms 59384 KB Output is correct
6 Correct 52 ms 59416 KB Output is correct
7 Correct 48 ms 59008 KB Output is correct
8 Correct 233 ms 71036 KB Output is correct
9 Correct 230 ms 65400 KB Output is correct
10 Correct 600 ms 75512 KB Output is correct
11 Correct 316 ms 75208 KB Output is correct
12 Correct 303 ms 74832 KB Output is correct
13 Correct 48 ms 59000 KB Output is correct
14 Correct 258 ms 70944 KB Output is correct
15 Correct 78 ms 60280 KB Output is correct
16 Correct 719 ms 75868 KB Output is correct
17 Correct 336 ms 74488 KB Output is correct
18 Correct 342 ms 74360 KB Output is correct
19 Correct 669 ms 108372 KB Output is correct
20 Correct 674 ms 108792 KB Output is correct
21 Correct 668 ms 111224 KB Output is correct
22 Correct 662 ms 108792 KB Output is correct
23 Correct 657 ms 108792 KB Output is correct
24 Correct 654 ms 108552 KB Output is correct
25 Correct 659 ms 108536 KB Output is correct
26 Correct 663 ms 111072 KB Output is correct
27 Correct 668 ms 111164 KB Output is correct
28 Correct 671 ms 108408 KB Output is correct
29 Correct 675 ms 108564 KB Output is correct
30 Correct 659 ms 108384 KB Output is correct