Submission #783772

#	Time	Username	Problem	Language	Result	Execution time	Memory
783772		awu	Pyramid Base (IOI08_pyramid_base)	C++14	35 / 100	5066 ms	47988 KiB

pyramid_base

#include <bits/extc++.h>
using namespace std;

// #define int long long
#define ll long long
// #define double long double
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) do{auto __y = x; cerr << #x << " = " << __y << endl;} while(0)

// #define endl "\n"
#define unordered_map __gnu_pbds::gp_hash_table
using pii = pair<int, int>;

// const ll inf = 1ll << 60;
const int inf = 1 << 28;
// const int MOD = 1e9 + 7;
// const int MOD = 1e9;

struct segtree {
  vector<int> t, lz;
  segtree(int s) {
    int n = 1;
    while(n < s) n *= 2;
    t.resize(n * 2);
    lz.resize(n * 2);
  }
  void push(int n, int tl, int tr) {
    t[n] += lz[n];
    if(tl + 1 != tr) {
      lz[n * 2] += lz[n];
      lz[n * 2 + 1] += lz[n];
    }
    lz[n] = 0;
  }
  void update(int ul, int ur, int v, int n = 1, int tl = 0, int tr = -1) {
    if(tr == -1) tr = t.size() / 2;
    if(ul >= tr || ur <= tl) return;
    if(ul <= tl && ur >= tr) {
      lz[n] += v;
      return;
    }
    push(n, tl, tr);
    int tm = (tl + tr) / 2;
    update(ul, ur, v, n * 2, tl, tm);
    update(ul, ur, v, n * 2 + 1, tm, tr);
    push(n * 2, tl, tm);
    push(n * 2 + 1, tm, tr);
    t[n] = min(t[n * 2], t[n * 2 + 1]);
  }
  int query(int ql, int qr, int n = 1, int tl = 0, int tr = -1) {
    if(tr == -1) tr = t.size() / 2;
    if(ql >= tr || qr <= tl) return inf;
    push(n, tl, tr);
    if(ql <= tl && qr >= tr) return t[n];
    int tm = (tl + tr) / 2;
    return min(query(ql, qr, n * 2, tl, tm), query(ql, qr, n * 2 + 1, tm, tr));
  }
};

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int m, n; cin >> m >> n;
  int b; cin >> b;
  assert(b == 0);
  int p; cin >> p;
  vector<pair<pii, pii>> obs(p);
  for(int i = 0; i < p; i++) {
    int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; x1--; y1--;
    obs[i] = {{x1, y1}, {x2, y2}};
  }
  int lo = 0, hi = min(m, n) + 1;
  while(lo + 1 < hi) {
    int mid = (lo + hi) / 2;
    struct event {
      int x, y1, y2, upd;
    };
    deque<event> ev;
    for(auto o : obs) {
      ev.push_back({o.f.f, o.f.s, o.s.s + mid - 1, 1});
      ev.push_back({o.s.f + mid - 1, o.f.s, o.s.s + mid - 1, -1});
    }
    ev.push_back({mid - 1, 0, 0, 0});
    sort(ev.begin(), ev.end(), [](event a, event b) {
      return a.x < b.x;
    });
    segtree st(n);
    bool ok = false;
    while(ev.size()) {
      int x = ev[0].x;
      while(ev.size() && ev[0].x == x) {
        st.update(ev[0].y1, ev[0].y2, ev[0].upd);
        ev.pop_front();
      }
      if(x >= mid - 1 && x < m && st.query(mid - 1, n) == 0) {
        ok = true;
        break;
      }
    }
    if(ok) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  cout << lo << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10