Submission #48276

#	Time	Username	Problem	Language	Result	Execution time	Memory
48276		choikiwon	허수아비 (JOI14_scarecrows)	C++17	0 / 100	394 ms	76932 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 a, int b, pii v, int l, int r, int n) {
        if(b < l || r < a) return;
        while(tree[n].size() && tree[n].back().second >= v.second) tree[n].pop_back();
        tree[n].push_back(v);
        if(a <= l && r <= b) return;
        int m = (l + r)>>1;
        upd(a, b, v, l, m, 2*n);
        upd(a, b, v, m + 1, r, 2*n + 1);
    }
    int quer(int ly, int ry, int x, int l, int r, int n) {
        if(l > r) return 0;

        /*
        cout << ly << ' ' << ry << ' ' << x << endl;
        for(int i = 0; i < tree[n].size(); i++) {
            cout << tree[n][i].first << ' ' << tree[n][i].second << endl;
        }
        //*/

        int s = 0, e = (int)tree[n].size() - 1, p = -1, q = -1;
        while(s <= e) {
            int m = (s + e)>>1;

            if(tree[n][m].first > x && tree[n][m].second < ry) {
                p = m;
                s = m + 1;
            }
            else e = m - 1;
        }
        s = 0, e = (int)tree[n].size() - 1;
        while(s <= e) {
            int m = (s + e)>>1;

            if(tree[n][m].second <= ly) {
                q = m;
                s = m + 1;
            }
            else e = m - 1;
        }
        if(q > p) q = p;

        //cout << "p, q " << p << ' ' << q << endl;

        if(l == r) return p - q;
        if(p > q) {
            x = max(x, tree[n][q + 1].first);
            ry = min(ry, tree[n][q + 1].second);
        }
        int m = (l + r)>>1;
        int R = quer(ly, ry, x, m + 1, r, 2*n + 1);
        return R + p - q;
    }
} 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--) {
        //cout << "i = " << i << endl;
        ans += bit.quer(P[i].second, N, -1, 0, N - 1, 1);
        bit.upd(P[i].second, N - 1, P[i], 0, N - 1, 1);
    }

    printf("%lld", ans);
}

Compilation message (stderr)

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:76: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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 85