Submission #115793

#	Time	Username	Problem	Language	Result	Execution time	Memory
115793		choikiwon	허수아비 (JOI14_scarecrows)	C++17	100 / 100	896 ms	82044 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];
int A[MN];
vector<int> X, Y;
unordered_map<int, int> dx, dy;

void add(int x, int v, vector<pii> &stk) {
    while(!stk.empty() && stk.back().first > v) stk.pop_back();
    stk.push_back(pii(v, x));
}

struct BIT {
    vector<vector<pii> > tree;
    void init() {
        tree = vector<vector<pii> >(4 * N);
    }
    void upd(int x, int v, int l, int r, int n) {
        if(x < l || r < x) return;
        add(v, x, tree[n]);
        if(l == r) return;
        int m = (l + r)>>1;
        upd(x, v, l, m, 2*n);
        upd(x, v, m + 1, r, 2*n + 1);
    }
    int quer(int a, int b, int &v, 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 = (int)tree[n].size();
            while(s <= e) {
                int m = (s + e)>>1;

                if(tree[n][m].second < v) {
                    p = m;
                    e = m - 1;
                }
                else s = m + 1;
            }
            if(p != tree[n].size()) v = tree[n].back().second;
            return (int)tree[n].size() - p;
        }
        int m = (l + r)>>1;
        int L = quer(a, b, v, l, m, 2*n);
        int R = quer(a, b, v, 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);
        X.push_back(P[i].first);
        Y.push_back(P[i].second);
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());
    Y.resize(unique(Y.begin(), Y.end()) - Y.begin());
    for(int i = 0; i < N; i++) {
        dx[X[i]] = i;
        dy[Y[i]] = i;
    }
    for(int i = 0; i < N; i++) {
        P[i].first = dx[P[i].first];
        P[i].second = dy[P[i].second];
        A[ P[i].first ] = P[i].second;
    }

    ll ans = 0;
    bit.init();
    for(int i = N - 1; i >= 0; i--) {
        int t = N;
        ans += bit.quer(A[i], N - 1, t, 0, N - 1, 1);
        bit.upd(A[i], 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:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(p != tree[n].size()) v = tree[n].back().second;
                ~~^~~~~~~~~~~~~~~~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:60: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