Submission #48281

#	Time	Username	Problem	Language	Result	Execution time	Memory
48281		choikiwon	허수아비 (JOI14_scarecrows)	C++17	100 / 100	614 ms	65512 KiB

scarecrows

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 200010;

int N;
pii P[MN];
vector<pii> ord;

struct BIT {
    vector<vector<pii> > tree;
    void init() {
        tree = vector<vector<pii> >(4 * N);
    }
    void upd(int idx, pii v, int l, int r, int n) {
        if(idx < l || r < idx) return;
        while(tree[n].size() && tree[n].back().second >= v.second) tree[n].pop_back();
        tree[n].push_back(v);
        if(l == r) return;
        int m = (l + r)>>1;
        upd(idx, v, l, m, 2*n);
        upd(idx, v, m + 1, r, 2*n + 1);
    }
    int quer(int a, int b, int &x, int l, int r, int n) {
        if(b < l || r < a) return 0;
        if(a <= l && r <= b) {
            int s = 0, e = (int)tree[n].size() - 1, p = tree[n].size();
            while(s <= e) {
                int m = (s + e)>>1;

                if(tree[n][m].first < x) {
                    p = m;
                    e = m - 1;
                }
                else s = m + 1;
            }

            if(p != tree[n].size()) x = min(x, tree[n].back().first);
            return (int)tree[n].size() - p;
        }

        int m = (l + r)>>1;
        int L = quer(a, b, x, l, m, 2*n);
        int R = quer(a, b, x, m + 1, r, 2*n + 1);
        return L + R;
    }
} bit;

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &P[i].first, &P[i].second);
        ord.push_back({ P[i].second, i });
    }
    sort(ord.begin(), ord.end());
    for(int i = 0; i < N; i++) P[ ord[i].second ].second = i;

    sort(P, P + N);

    ll ans = 0;
    bit.init();
    for(int i = N - 1; i >= 0; i--) {
        int x = 2e9;
        ans += bit.quer(P[i].second, N - 1, x, 0, N - 1, 1);
        bit.upd(P[i].second, P[i], 0, N - 1, 1);
    }

    printf("%lld", ans);
}

Compilation message (stderr)

scarecrows.cpp: In member function 'int BIT::quer(int, int, int&, int, int, int)':
scarecrows.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(p != tree[n].size()) x = min(x, tree[n].back().first);
                ~~^~~~~~~~~~~~~~~~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &P[i].first, &P[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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