oj.uz

Submission #39675

# Submission time Handle Problem Language Result Execution time Memory
39675 2018-01-17T04:46:47 Z deletend Wall (IOI14_wall) C++14
0 / 100
 0 ms 49080 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define mod (ll)(1e9+7)

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

class SegTree {
private:
public:
  int dat[2 * 2000000 - 1];
  bool d;
  void query(int a, int b, int k, int l, int r, int nk);
  void update(int k, int a);
};

SegTree mx, mn;
int n = 1, plus[2 * 2000000 - 1];

void SegTree::update(int k, int a) {
  dat[k] = a;
  while(k > 0) {
    k = (k - 1) / 2;
    if(d) dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
    else dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
  }
}

void SegTree::query(int a, int b, int k, int l, int r, int nk) {
  if(r <= a || b <= l) return;
  if(a <= l && r <= b) {
    if(d) {
      if(dat[k] <= nk) {
        mx.update(k, nk);
        mn.update(k, nk);
      }else if(mn.dat[k] < nk) {
        query(a, b, k * 2 + 1, l, (l + r) / 2, nk);
        query(a, b, k * 2 + 2, (l + r) / 2, r, nk);
      }
    }else {
      if(dat[k] >= nk) {
        mx.update(k, nk);
        mn.update(k, nk);
      }else if(mx.dat[k] > nk) {
        query(a, b, k * 2 + 1, l, (l + r) / 2, nk);
        query(a, b, k * 2 + 2, (l + r) / 2, r, nk);
      }
    }
  }else {
    query(a, b, k * 2 + 1, l, (l + r) / 2, nk);
    query(a, b, k * 2 + 2, (l + r) / 2, r, nk);
  }
}

void solve(int k, int l, int r, int f[]) {
  if(mx.dat[k] == mn.dat[k]) {
    rep(i, l, r) {
      f[i] = mx.dat[k];
    }
  }else {
    solve(k * 2 + 1, l, (l + r) / 2, f);
    solve(k * 2 + 1, (l + r) / 2, r, f);
  }
}

void buildWall(int n_, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  while(n < n_) n *= 2;
  mx.d = 1, mn.d = 0;
  rep(i, 0, n * 2 - 1) {
    mx.dat[i] = 0;
    mn.dat[i] = 0;
  }
  rep(i, 0, k) {
    if(op[i] == 1) mx.query(left[i], right[i], 0, 0, n, height[i]);
    else mn.query(left[i], right[i], 0, 0, n, height[i]);
  }

  solve(0, 0, n, finalHeight);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 49080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 49080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 49080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 49080 KB Output isn't correct
2 Halted 0 ms 0 KB -