oj.uz

Submission #414274

# Submission time Handle Problem Language Result Execution time Memory
414274 2021-05-30T09:45:42 Z Alex_tz307 Sails (IOI07_sails) C++17
0 / 100
 36 ms 7320 KB 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;
using int64 = long long;

struct SegTree {
  int Size;
  vector<int> tree, lazy;

  SegTree(int N) {
    Size = 1;
    while (Size < N)
      Size <<= 1;
    tree.resize(Size << 1);
    lazy.resize(Size << 1);
  }

  void add_back(int x, int lx, int rx, int poz) {
    if (lx == rx) {
      tree[x] = INF;
      return;
    }
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    if (poz <= mid)
      add_back(lSon, lx, mid, poz);
    else add_back(rSon, mid + 1, rx, poz);
    tree[x] = max(tree[lSon], tree[rSon]);
  }

  void push(int x) {
    if (lazy[x] == 0)
      return;
    for (int i = 0; i < 2; ++i) {
      int son = x << 1 | i;
      tree[son] += lazy[x];
      lazy[son] += lazy[x];
    }
    lazy[x] = 0;
  }

  void update(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      ++tree[x], ++lazy[x];
      return;
    }
    push(x);
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    if (st <= mid)
      update(lSon, lx, mid, st, dr);
    if (mid < dr)
      update(rSon, mid + 1, rx, st, dr);
    tree[x] = max(tree[lSon], tree[rSon]);
  }

  int lower(int x, int lx, int rx, int val) {
    if (lx == rx)
      return lx;
    push(x);
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    if (tree[lSon] >= val)
      return lower(lSon, lx, mid, val);
    return lower(rSon, mid + 1, rx, val);
  }

  int upper(int x, int lx, int rx, int val) {
    if (lx == rx)
      return lx;
    push(x);
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    if (tree[lSon] > val)
      return upper(lSon, lx, mid, val);
    return upper(rSon, mid + 1, rx, val);
  }

  int get_val(int x, int lx, int rx, int poz) {
    if (lx == rx)
      return tree[x];
    push(x);
    int mid = (lx + rx) >> 1;
    if (poz <= mid)
      return get_val(x << 1, lx, mid, poz);
    return get_val(x << 1 | 1, mid + 1, rx, poz);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  vector<pair<int,int>> m(n);
  for (auto &p : m)
    cin >> p.first >> p.second;
  sort(m.begin(), m.end());
  int H = m.back().first + 1;
  SegTree tree(H);
  tree.add_back(1, 1, H, H);
  for (auto p : m) {
    int h, k;
    tie(h, k) = p;
    int val = tree.get_val(1, 1, H, k);
    int last_poz_update = tree.lower(1, 1, H, val) - 1;
    if (last_poz_update > 0) {
      tree.update(1, 1, H, 1, last_poz_update);
      k -= last_poz_update;
    }
    if (k == 0)
      continue;
    last_poz_update = min(h, tree.upper(1, 1, H, val) - 1);
    tree.update(1, 1, H, last_poz_update - k + 1, last_poz_update);
  }
  int64 ans = 0;
  for (int h = 1; h < H; ++h) {
    int64 sails = tree.get_val(1, 1, H, h);
    ans += (sails * (sails - 1)) >> 1;
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 2252 KB Execution killed with signal 11

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 3828 KB Execution killed with signal 11

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 6644 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 7108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 7320 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -