oj.uz

Submission #783772

# Submission time Handle Problem Language Result Execution time Memory
783772 2023-07-15T10:07:58 Z awu Pyramid Base (IOI08_pyramid_base) C++14
35 / 100
 5000 ms 47988 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 620 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2432 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 16880 KB Output is correct
2 Correct 130 ms 16888 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 16864 KB Output is correct
2 Correct 130 ms 16968 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 32400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5066 ms 40076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 47988 KB Time limit exceeded
2 Halted 0 ms 0 KB -