Submission #1067322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067322		juicy	허수아비 (JOI14_scarecrows)	C++17	100 / 100	926 ms	16868 KiB

scarecrows

#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 5;

int n;
long long res;
int ft[N], p[N];

void upd(int i, int x) {
  for (; i <= n; i += i & -i) {
    ft[i] += x;
  }
}

int qry(int i) {
  int res = 0;
  for (; i; i -= i & -i) {
    res += ft[i];
  }
  return res;
}

int qry(int l, int r) {
  return qry(r) - qry(l - 1);
}

void add(int x) {
  if (x > 0) {
    upd(x, 1);
  } else {
    upd(-x, -1);
  }
}

void dc(int L, int R) {
  if (L == R) {
    return;
  }
  int md = (L + R) / 2;
  dc(L, md); dc(md + 1, R);
  set<int> st;
  vector<array<int, 2>> queries, events;
  for (int i = md + 1; i <= R; ++i) {
    auto it = st.upper_bound(p[i]);
    int j = it != st.begin() ? *prev(it) + 1 : 1;
    queries.push_back({p[i], j});
    st.insert(p[i]);
  }
  set<int>().swap(st);
  for (int i = md; i >= L; --i) {
    auto it = st.lower_bound(p[i]);
    int j = it != st.end() ? *it : n + 1;
    events.push_back({p[i], p[i]});
    events.push_back({j, -p[i]});
    st.insert(p[i]);
  }
  set<int>().swap(st);
  sort(queries.begin(), queries.end());
  sort(events.begin(), events.end());
  int j = 0;
  for (auto [r, l] : queries) {
    while (j < events.size() && events[j][0] <= r) {
      add(events[j++][1]);
    }
    res += qry(l, r);
  }
  while (j < events.size()) {
    add(events[j++][1]);
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  vector<array<int, 2>> pt(n);
  vector<int> comp;
  for (int i = 0; i < n; ++i) {
    cin >> pt[i][0] >> pt[i][1];
    comp.push_back(pt[i][1]);
  }
  sort(pt.begin(), pt.end());
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  for (int i = 0; i < n; ++i) {
    p[i] = lower_bound(comp.begin(), comp.end(), pt[i][1]) - comp.begin() + 1;
  }
  dc(0, n - 1);
  cout << res;
  return 0;
}

Compilation message (stderr)

scarecrows.cpp: In function 'void dc(int, int)':
scarecrows.cpp:70:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     while (j < events.size() && events[j][0] <= r) {
      |            ~~^~~~~~~~~~~~~~~
scarecrows.cpp:75:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   while (j < events.size()) {
      |          ~~^~~~~~~~~~~~~~~

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