oj.uz

Submission #156055

# Submission time Handle Problem Language Result Execution time Memory
156055 2019-10-03T03:49:36 Z IOrtroiii 허수아비 (JOI14_scarecrows) C++14
0 / 100
 4000 ms 7364 KB 
#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

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);
          ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 632 KB Output is correct
2 Incorrect 17 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 7364 KB Time limit exceeded
2 Halted 0 ms 0 KB -