oj.uz

Submission #520427

# Submission time Handle Problem Language Result Execution time Memory
520427 2022-01-30T00:08:32 Z pokmui9909 허수아비 (JOI14_scarecrows) C++17
100 / 100
 2460 ms 33212 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 16708 KB Output is correct
2 Correct 79 ms 16708 KB Output is correct
3 Correct 80 ms 16688 KB Output is correct
4 Correct 97 ms 16748 KB Output is correct
5 Correct 86 ms 16696 KB Output is correct
6 Correct 82 ms 16672 KB Output is correct
7 Correct 81 ms 16720 KB Output is correct
8 Correct 83 ms 16692 KB Output is correct
9 Correct 83 ms 16688 KB Output is correct
10 Correct 81 ms 16684 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 17112 KB Output is correct
2 Correct 122 ms 17124 KB Output is correct
3 Correct 123 ms 17092 KB Output is correct
4 Correct 118 ms 17264 KB Output is correct
5 Correct 112 ms 17128 KB Output is correct
6 Correct 114 ms 17136 KB Output is correct
7 Correct 115 ms 17220 KB Output is correct
8 Correct 112 ms 17108 KB Output is correct
9 Correct 124 ms 17140 KB Output is correct
10 Correct 118 ms 17144 KB Output is correct
11 Correct 117 ms 17108 KB Output is correct
12 Correct 130 ms 17092 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1935 ms 31676 KB Output is correct
2 Correct 2435 ms 33036 KB Output is correct
3 Correct 2083 ms 32924 KB Output is correct
4 Correct 1936 ms 32936 KB Output is correct
5 Correct 2170 ms 32944 KB Output is correct
6 Correct 2350 ms 32944 KB Output is correct
7 Correct 2378 ms 32900 KB Output is correct
8 Correct 2426 ms 33124 KB Output is correct
9 Correct 1913 ms 33000 KB Output is correct
10 Correct 2175 ms 33180 KB Output is correct
11 Correct 2311 ms 32996 KB Output is correct
12 Correct 2428 ms 32992 KB Output is correct
13 Correct 2455 ms 33040 KB Output is correct
14 Correct 1946 ms 33024 KB Output is correct
15 Correct 2338 ms 33032 KB Output is correct
16 Correct 2460 ms 32996 KB Output is correct
17 Correct 1481 ms 26496 KB Output is correct
18 Correct 2404 ms 33084 KB Output is correct
19 Correct 2395 ms 33048 KB Output is correct
20 Correct 2348 ms 33212 KB Output is correct