oj.uz

Submission #909624

# Submission time Handle Problem Language Result Execution time Memory
909624 2024-01-17T09:56:48 Z MilosMilutinovic 허수아비 (JOI14_scarecrows) C++14
100 / 100
 1050 ms 25900 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> x(n);
  vector<int> y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  vector<int> xs;
  vector<int> ys;
  for (int i = 0; i < n; i++) {
    xs.push_back(x[i]);
    ys.push_back(y[i]);
  }
  sort(xs.begin(), xs.end());
  sort(ys.begin(), ys.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  ys.erase(unique(ys.begin(), ys.end()), ys.end());
  for (int i = 0; i < n; i++) {
    x[i] = (int) (lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin());
    y[i] = (int) (lower_bound(ys.begin(), ys.end(), y[i]) - ys.begin());
  }
  {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return x[i] < x[j];
    });
    vector<int> new_x(n);
    vector<int> new_y(n);
    for (int i = 0; i < n; i++) {
      new_x[i] = x[order[i]];
      new_y[i] = y[order[i]];
    }
    x = new_x;
    y = new_y;
  }
  vector<int> fenw(n + 1);
  auto Modify = [&](int p, int v) {
    for (p++; p <= n; p += p & -p) {
      fenw[p] += v;
    }
  };
  auto Query = [&](int p) {
    int res = 0;
    for (p++; p; p -= p & -p) {
      res += fenw[p];
    }
    return res;
  };
  long long ans = 0;
  function<void(int, int)> Solve = [&](int L, int R) {
    if (L >= R) {
      return;
    }
    int mid = L + R >> 1;
    vector<array<int, 4>> ev;
    set<int> st;
    for (int i = mid; i >= L; i--) {
      auto it = st.lower_bound(y[i]);
      if (it == st.end()) {
        ev.push_back({y[i], n - 1, 1, i});
      } else {
        ev.push_back({y[i], *it - 1, 1, i});
      } 
      st.insert(y[i]);
    }
    st.clear();
    for (int i = mid + 1; i <= R; i++) {
      auto it = st.lower_bound(y[i]);
      if (it == st.begin()) {
        ev.push_back({0, y[i], 0, i});
      } else {
        ev.push_back({*prev(it) + 1, y[i], 0, i});
      }
      st.insert(y[i]);
    }
    sort(ev.begin(), ev.end());
    for (auto& p : ev) {
      if (p[2] == 0) {
        Modify(p[1], +1);
      } else {
        ans += Query(p[1]) - Query(p[0] - 1);
      }
    }
    for (auto& p : ev) {
      if (p[2] == 0) {
        Modify(p[1], -1);
      }
    }
    Solve(L, mid);
    Solve(mid + 1, R);
  };
  Solve(0, n - 1);
  cout << ans << '\n';
  return 0;
}

Compilation message

scarecrows.cpp: In lambda function:
scarecrows.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = L + R >> 1;
      |               ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 860 KB Output is correct
2 Correct 14 ms 860 KB Output is correct
3 Correct 12 ms 860 KB Output is correct
4 Correct 11 ms 860 KB Output is correct
5 Correct 13 ms 848 KB Output is correct
6 Correct 16 ms 860 KB Output is correct
7 Correct 15 ms 860 KB Output is correct
8 Correct 9 ms 856 KB Output is correct
9 Correct 14 ms 1084 KB Output is correct
10 Correct 15 ms 848 KB Output is correct
11 Correct 15 ms 856 KB Output is correct
12 Correct 10 ms 860 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 23572 KB Output is correct
2 Correct 1008 ms 24952 KB Output is correct
3 Correct 787 ms 25320 KB Output is correct
4 Correct 708 ms 24708 KB Output is correct
5 Correct 862 ms 25212 KB Output is correct
6 Correct 915 ms 24852 KB Output is correct
7 Correct 964 ms 24700 KB Output is correct
8 Correct 1050 ms 24760 KB Output is correct
9 Correct 625 ms 24700 KB Output is correct
10 Correct 864 ms 25536 KB Output is correct
11 Correct 941 ms 24844 KB Output is correct
12 Correct 1024 ms 25900 KB Output is correct
13 Correct 996 ms 24580 KB Output is correct
14 Correct 641 ms 24728 KB Output is correct
15 Correct 934 ms 24672 KB Output is correct
16 Correct 1035 ms 25784 KB Output is correct
17 Correct 584 ms 16012 KB Output is correct
18 Correct 986 ms 24704 KB Output is correct
19 Correct 975 ms 24836 KB Output is correct
20 Correct 954 ms 25096 KB Output is correct