제출 #909624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
909624		MilosMilutinovic	허수아비 (JOI14_scarecrows)	C++14	100 / 100	1050 ms	25900 KiB

scarecrows

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85