Submission #115473

#TimeUsernameProblemLanguageResultExecution timeMemory
115473parkj2180허수아비 (JOI14_scarecrows)C++14
0 / 100
131 ms47460 KiB
#include<cstdio> #include<iostream> #include<vector> #include<stack> #include<algorithm> using namespace std; #define MAX 1000000009 int n, ans, before, chk; pair<int, int> arr[200200]; pair<int, int> asdfa[200200]; vector< pair<int, int> > dp[500200]; int asdf(int index, int x, int start, int end) { if (start == end) return start; int mid = (start + end) / 2; if (dp[index][mid].first < x&&dp[index][mid + 1].first > x) return mid; if (dp[index][mid].first > x) { return asdf(index, x, start, mid); } else { return asdf(index, x, mid + 1, end); } } void f(int index, int start, int end, int left, int right, int x) { if (chk == 1) return; if (left > end || right < start) return; else if (left <= start && right >= end) { if (x < dp[index][0].first) return; int s = asdf(index, x, 0, dp[index].size() - 1); if (before > dp[index][s].first) { chk = 1; return; } int r = asdf(index, before, 0, dp[index].size() - 1); before = dp[index][s].first; if (r >= 0) { ans += dp[index][s].second - dp[index][r-1].second; } else ans += dp[index][s].second; } else { int mid = (start + end) / 2; f(index * 2 + 1, mid + 1, end, left, right, x); f(index * 2, start, mid, left, right, x); } } int main() { scanf("%d", &n); for (int i = 0; i<n; i++) { scanf("%d%d", &arr[i].first, &arr[i].second); arr[i].first++; arr[i].second++; } sort(arr, arr + n); for (int i = 0; i<n; i++) { asdfa[i].first = arr[i].second; asdfa[i].second = i; } sort(asdfa, asdfa + n); int t = 1, depth; for (depth = 1; t<n; depth++) t = t * 2; for (int i = 0; i<n; i++) { dp[i + t].push_back(make_pair(asdfa[i].second+1, 1)); } for (int i = n; i<t; i++) { dp[i + t].push_back(make_pair(MAX+i, 1)); } for (int i = t - 1; i >= 1; i--) { stack < pair<int, int> > st; int cnt = 0; for (int j = 0; j<dp[2 * i].size(); j++) { st.push(dp[2 * i][dp[2 * i].size()-j-1]); } int j = 1; while (1) { if (j == dp[2 * i + 1].size()+1) { while (st.empty() != 1) { pair<int, int> temp = st.top(); temp.second += cnt; dp[i].push_back(temp); st.pop(); } break; } else if (st.empty() == 1) { while (j != dp[2*i+1].size()+1) { pair<int, int> temp = dp[2 * i + 1][j-1]; dp[i].push_back(temp); j++; } break; } else if (st.top().first<dp[2 * i + 1][j-1].first) { pair<int, int> temp = st.top(); temp.second += cnt; dp[i].push_back(temp); st.pop(); } else if (st.top().first>dp[2 * i + 1][j-1].first) { dp[i].push_back(dp[2 * i + 1][j - 1]); j++; cnt++; } } } for (int i = 0; i < n; i++) { before = 0; chk = 0; int x = dp[i+t][0].first; int y = i+1; f(1, 1, t, 1, y-1, x); } printf("%d", ans); return 0; }

Compilation message (stderr)

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j<dp[2 * i].size(); j++) {
                   ~^~~~~~~~~~~~~~~~~
scarecrows.cpp:76:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j == dp[2 * i + 1].size()+1) {
        ~~^~~~~~~~~~~~~~~~~~~~~~~~~
scarecrows.cpp:86:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (j != dp[2*i+1].size()+1) {
            ~~^~~~~~~~~~~~~~~~~~~~~
scarecrows.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
scarecrows.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &arr[i].first, &arr[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...