oj.uz

Submission #745591

# Submission time Handle Problem Language Result Execution time Memory
745591 2023-05-20T14:20:58 Z Username4132 Wall (IOI14_wall) C++14
0 / 100
 169 ms 14104 KB 
#include "wall.h"

#include<iostream>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define F first
#define S second

const int MAXN=1000010, MAXH=100010;
int n, he;

pii combine(pii a, pii b){
  if(b.S<=a.F) return {b.S - 1, b.S};
  else if(a.S<=b.F) return {b.F, b.F + 1};
  else return {max(a.F, b.F), min(a.S, b.S)};
}

pii tr[2*MAXN];

void apply(int p, pii value){
  tr[p]=combine(tr[p], value);
}

void push(int p){
  for(int s=he; s>0; --s){
    int i=(p>>s);
    apply(i<<1, tr[i]);
    apply(i<<1|1, tr[i]);
    tr[i]={0, MAXH};
  }
}

void modify(int l, int r, pii value){
  l+=n, r+=n;
  push(l);
  push(r-1);
  for(; l<r; l>>=1, r>>=1){
    if(l&1) apply(l++, value);
    if(r&1) apply(--r, value);
  }
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n=N; he=8*sizeof(int) - __builtin_clz(n);
  forn(i, 2*n) tr[i]={0, MAXH};
  forn(i, k){
    pii interval = op[i]==1? make_pair(height[i], n) : make_pair(0, height[i]+1);
    modify(left[i], right[i]+1, interval);
  }
  for(int i=1; i<n; ++i){
    apply(i<<1, tr[i]);
    apply(i<<1|1, tr[i]);
  }
  forn(i, n) finalHeight[i]=tr[n+i].F;
  return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 3 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Incorrect 169 ms 14104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -