oj.uz

Submission #39684

# Submission time Handle Problem Language Result Execution time Memory
39684 2018-01-17T08:52:25 Z deletend Wall (IOI14_wall) C++14
0 / 100
 279 ms 56916 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);
}

struct K {
  int l, r, h, k;
};

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

SegTree mx, mn, da;
int n = 1;

void update(int k, int a) {
  da.dat[k] = a;
  mx.dat[k] = a;
  mn.dat[k] = a;
  while(k > 0) {
    k = (k - 1) / 2;
    mx.dat[k] = max(mx.dat[k * 2 + 1], mx.dat[k * 2 + 2]);
    mn.dat[k] = min(mn.dat[k * 2 + 1], mn.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) {
        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) {
        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 f[]) {
  int t = 1, kn = 1;
  while(n > kn) {
    kn *= 2;
    t++;
  }
  int j = n - 1;
  int r = 1;
  int z = n * 2 - 1;
  while(1) {
    rep(k, j, z) {
      if(da.dat[k] != -1) {
        rep(m, 0, r) {
          if(!f[m + (k - j) * r]) f[m + (k - j) * r] = da.dat[k];
        }
        cout << endl;
      }
    }
    if(j == 0) break;
    r++;
    z = j;
    j /= 2;
  }
}

void SegTree::out() {
  int t = 0, kn = 1;
  while(n > kn) {
    kn *= 2;
    t++;
  }
  int h[t + 1] = {0, 1};
  rep(i, 2, t + 1) h[i] = h[i - 1] * 2 + 1;
  queue<K> q;
  K k = {0, n, 1, 0};
  q.push(k);
  while(!q.empty()) {
    queue<K> nq;
    K pp = q.front();
    if(pp.k > n) break;
    rep(i, 0, h[t]) cout << " ";
    while(!q.empty()) {
      K p = q.front();
      q.pop();
      cout << dat[p.k];
      if(t > 0) rep(i, 0, h[t + 1]) cout << " ";
      else cout << " ";
      K lk = {p.l, (p.l + p.r) / 2, p.h * 2, p.k * 2 + 1};
      K rk = {(p.l + p.r) / 2, p.r, p.h * 2, p.k * 2 + 2};
      nq.push(lk);
      nq.push(rk);
    }
    t--;
    cout << endl;
    q = nq;
  }
}
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;
    da.dat[i] = -1;
  }
  rep(i, 0, k) {
    if(op[i] == 1) mx.query(left[i], right[i] + 1, 0, 0, n, height[i]);
    else mn.query(left[i], right[i] + 1, 0, 0, n, height[i]);
    // mx.out();
    // cout << endl;
    // mn.out();
    // cout << endl;
  }
  //da.out();

  solve(0, finalHeight);
}

// int main() {
//   int nn, k;
//   cin >> nn >> k;
//   int op[20000], left[20000], right[20000], height[20000], finalHeight[20000];
//   rep(i, 0, k) {
//     cin >> op[i] >> left[i] >> right[i] >> height[i];
//   }
//   buildWall(nn, k, op, left, right, height, finalHeight);
//
  // mx.out();
  // cout << endl << endl;
  // mn.out();
//
//   rep(i, 0, nn) {
//     cout << finalHeight[i] << " ";
//   }
//   cout << endl;
// }

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49092 KB Output is correct
2 Correct 196 ms 56916 KB Output is correct
3 Incorrect 279 ms 52340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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