oj.uz

Submission #1080910

# Submission time Handle Problem Language Result Execution time Memory
1080910 2024-08-29T15:54:40 Z juicy Sails (IOI07_sails) C++17
100 / 100
 43 ms 4692 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

int n;
int dif[N];
set<int> st;

void add(int i, int x) {
  dif[i] += x;
  if (dif[i]) {
    st.insert(i);
  } else {
    st.erase(i);
  }
}

void upd(int i, int j) {
  add(i, 1);
  add(j + 1, -1);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  
  cin >> n;
  vector<array<int, 2>> a(n);
  for (auto &x : a) {
    cin >> x[0] >> x[1];
  }
  sort(a.begin(), a.end());
  int l = a.back()[0];
  st.insert(1);
  st.insert(l + 1);
  for (auto [h, k] : a) {
    auto it = st.upper_bound({h - k + 1});
    int l = *prev(it), r = *it - 1;
    if (r < h) {
      upd(r + 1, h);
      k -= h - r;
    }
    if (k > 0) {
      upd(l, l + k - 1);
    }
  }
  long long res = 0;
  int cnt = 0;
  for (int i = 1; i <= l; ++i) {
    cnt += dif[i];
    res += (long long) cnt * (cnt - 1) / 2;
  }
  cout << res;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 856 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 11 ms 860 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2352 KB Output is correct
2 Correct 24 ms 2908 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4692 KB Output is correct
2 Correct 19 ms 2144 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3420 KB Output is correct
2 Correct 20 ms 2348 KB Output is correct