oj.uz

답안 #117442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117442 2019-06-15T23:42:06 Z dragonslayerit 벽 (IOI14_wall) C++14
0 / 100
 210 ms 39112 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 N;

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

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

struct Node query(int a,int b){
  struct Node lsum,rsum;
  for(a+=N,b+=N;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[]){
  N=n;
  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+n],alt[x]);
      update(x);
    }
    finalHeight[i]=query(0,n).eval(0);
  }
  return;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Incorrect 22 ms 23936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Incorrect 210 ms 39112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Incorrect 23 ms 24000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Incorrect 22 ms 24064 KB Output isn't correct
3 Halted 0 ms 0 KB -