Submission #156055

#TimeUsernameProblemLanguageResultExecution timeMemory
156055IOrtroiii허수아비 (JOI14_scarecrows)C++14
0 / 100
4043 ms7364 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int n; scanf("%d", &n); vector<int> x(n); vector<int> y(n); { vector<pair<int, int>> ps; for (int i = 0; i < n; ++i) { int x, y; scanf("%d %d", &x, &y); ps.emplace_back(x, y); } sort(ps.begin(), ps.end()); for (int i = 0; i < n; ++i) { x[i] = ps[i].first; y[i] = ps[i].second; } } ll ans = 0; function<void(int, int)> solve = [&](int l, int r) { if (l == r) { return; } int md = (l + r) >> 1; vector<tuple<int, int, int>> vals; for (int i = l; i <= md; ++i) { vals.emplace_back(y[i], x[i], -1); } for (int i = md + 1; i <= r; ++i) { vals.emplace_back(y[i], x[i], +1); } sort(vals.begin(), vals.end()); vector<pair<int, int>> st1, st2; auto Assert = [&](vector<pair<int, int>> ps) { int sz = ps.size(); for (int i = 1; i < sz; ++i) { assert(ps[i].first > ps[i - 1].first); assert(ps[i].second < ps[i - 1].second); } }; for (auto v : vals) { int y, x, tp; tie(y, x, tp) = v; if (tp == -1) { while (st1.size() && x > st1.back().second) { st1.pop_back(); } st1.emplace_back(y, x); } else { int lim = -1; while (st2.size() && x > st2.back().second) { lim = max(lim, st2.back().first); st2.pop_back(); } int fs = lower_bound(st1.begin(), st1.end(), make_pair(lim, 0)) - st1.begin(); ans += (st1.size()) - fs; st2.emplace_back(y, x); } Assert(st1); Assert(st2); } solve(l, md); solve(md + 1, r); }; solve(0, n - 1); printf("%lld\n", ans); }

Compilation message (stderr)

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:9:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &n);
    ~~~~~^~~~~~~~~~
scarecrows.cpp:16:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%d %d", &x, &y);
          ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...