Submission #520427

#	Time	Username	Problem	Language	Result	Execution time	Memory
520427		pokmui9909	허수아비 (JOI14_scarecrows)	C++17	100 / 100	2460 ms	33212 KiB

scarecrows

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

#define x first
#define y second
const ll S = (1 << 19);
const ll INF = 1e15;
struct MaxSegTree{
    ll T[2 * S] = {};
    void update(ll k, ll v) { update(1, 1, S, k + 1, v); }
    ll query(ll l, ll r) { return query(1, 1, S, l + 1, r + 1); }
    void update(ll node, ll s, ll e, ll k, ll v){
        if (s == e){
            T[node] = v;
            return;
        }
        ll m = (s + e) / 2;
        ll lch = 2 * node, rch = 2 * node + 1;
        if (k <= m) update(lch, s, m, k, v);
        else update(rch, m + 1, e, k, v);
        ll x = T[lch], y = T[rch];
        T[node] = max(x, y);
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if (e < l || s > r) return -INF;
        if (l <= s && e <= r) return T[node];
        ll m = (s + e) / 2;
        ll lch = 2 * node, rch = 2 * node + 1;
        ll x = query(lch, s, m, l, r), y = query(rch, m + 1, e, l, r);
        return max(x, y);
    }
};
MaxSegTree T1, T2;
ll N;
pair<ll, ll> A[200005];
ll ans = 0;

void dnc(ll L, ll R){
    if(L >= R) return;
    ll m = (L + R) / 2;
    dnc(L, m);
    dnc(m + 1, R);
    vector<pair<ll, ll>> V;
    for(int i = L; i <= R; i++){
        V.push_back({A[i].y, i});
    }
    sort(V.begin(), V.end(), greater<pair<ll, ll>>());
    vector<ll> B;
    for(int i = 0; i < V.size(); i++){
        ll K = V[i].y;
        if(K <= m){
            ll S = T1.query(K, m);
            if(S == -INF) S = 0;
            ll E = -T2.query(S, i);
            ll idx = lower_bound(B.begin(), B.end(), E) - B.begin();
            ans += B.size() - idx;
            T1.update(K, i);
        } else {
            while(!B.empty() && B.back() > K) B.pop_back();
            B.push_back(K);
            T2.update(i, -K);
        }
    }
    for(int i = 0; i < V.size(); i++){
        ll K = V[i].y;
        T1.update(K, -INF);
        T2.update(K, -INF);
        T1.update(i, -INF);
        T2.update(i, -INF);
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    for(int i = 1; i <= S; i++){
        T1.update(i, -INF);
        T2.update(i, -INF);
    }
    cin >> N;
    vector<ll> X, Y;
    for(int i = 1; i <= N; i++){
        cin >> A[i].x >> A[i].y;
        X.push_back(A[i].x);
        Y.push_back(A[i].y);
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    sort(A + 1, A + N + 1);
    for(int i = 1; i <= N; i++){
        A[i].x = lower_bound(X.begin(), X.end(), A[i].x) - X.begin() + 1;
        A[i].y = lower_bound(Y.begin(), Y.end(), A[i].y) - Y.begin() + 1;
    }
    dnc(1, N);
    cout << ans;
}

Compilation message (stderr)

scarecrows.cpp: In function 'void dnc(ll, ll)':
scarecrows.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i < V.size(); i++){
      |                    ~~^~~~~~~~~~
scarecrows.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i < V.size(); i++){
      |                    ~~^~~~~~~~~~

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