Submission #1322878

#TimeUsernameProblemLanguageResultExecution timeMemory
1322878syanvuBodyguards (CEOI10_bodyguards)C++20
50 / 100
152 ms327680 KiB
// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(v) v.begin(),v.end()
using namespace std;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e4 + 1, MX = 40, inf = 1e18;


struct seg{
    vector<int> t, L, R, add;
    int timer = 1;

    seg(){
        t.resize(N);
        L.resize(N);
        R.resize(N);
        add.resize(N);
        timer = 1;
    }
    void push(int v, int tl, int tr){
        t[v] += (tr - tl + 1) * add[v];
        if(tl < tr){
            add[L[v]] += add[v];
            add[R[v]] += add[v];
        }
        add[v] = 0;
    }

    void upd(int v, int tl, int tr, int l, int r, int x){
        if(!L[v]) L[v] = ++timer;
        if(!R[v]) R[v] = ++timer;
        push(v, tl, tr);
        if(tl > r || l > tr) return;
        if(tl >= l && r >= tr){
            add[v] += x;
            push(v, tl, tr);
            return;
        }
        int mid = (tl + tr) / 2;
        upd(L[v], tl, mid, l, r, x);
        upd(R[v], mid + 1, tr, l, r, x);
        t[v] = t[L[v]] + t[R[v]];
    }
    int get(int v, int tl, int tr, int l, int r){
        if(tl > r || l > tr) return 0ll;
        if(!L[v]) L[v] = ++timer;
        if(!R[v]) R[v] = ++timer;
        push(v, tl, tr);
        if(tl >= l && r >= tr) return t[v];
        int mid = (tl + tr) / 2;
        return get(L[v], tl, mid, l, r) + get(R[v], mid + 1, tr, l, r);
    }
};

seg tr, tc;

void solve(){
    int n;
    cin >> n;
    pair<int, int> r[n + 1];
    int sumr = 0, sumc = 0, br = 0, bc = 0;
    for(int i = 1; i <= n; i++){
        cin >> r[i].first >> r[i].second;
        br += r[i].first * r[i].second;
    }
    int m;
    cin >> m;
    pair<int, int> c[m + 1];
    for(int i = 1; i <= m; i++){
        cin >> c[i].first >> c[i].second;
        bc += c[i].first * c[i].second;
    }
    if(br != bc){
        cout << 0 << '\n';
        return;
    }
    sort(r + 1, r + n + 1);
    sort(c + 1, c + m + 1);
    for(int i = 1; i <= m; i++){
        tc.upd(1, 1, 1e18, sumc + 1, sumc + c[i].second, c[i].first);
        sumc += c[i].second;
    }
    for(int i = 1; i <= n; i++){
        tr.upd(1, 1, 1e18, sumr + 1, sumr + r[i].second, r[i].first);
        sumr += r[i].second;
    }
    reverse(r + 1, r + n + 1);
    reverse(c + 1, c + m + 1);
    int pr1[sumc + 1] = {}, pr2[sumr + 1] = {};
    int cur = 0;
    for(int i = 1; i <= n; i++){
        if(r[i].first > sumc){
            cout << 0 << '\n';
            return;
        }
        tc.upd(1, 1, 1e18, sumc - r[i].first + 1, sumc, -r[i].second);
        if(tc.get(1, 1, 1e18, 1, sumc - r[i].first + 1) < 0){
            cout << 0 << '\n';
            return;
        }
    }
    for(int i = 1; i <= m; i++){
        if(c[i].first > sumr){
            cout << 0 << '\n';
            return;
        }
        tr.upd(1, 1, 1e18, sumr - c[i].first + 1, sumr, -c[i].second);
        // cout << i << ' ';
        if(tr.get(1, 1, 1e18, 1, sumr - c[i].first + 1) < 0){
            cout << 0 << '\n';
            return;
        }
    }
    sumr = 0, sumc = 0;
    for(int i = 1; i <= m; i++){
        if(tc.get(1, 1, 1e18, 1, sumc + 1) < 0 || tc.get(1, 1, 1e18, 1, sumc + c[i].second) < 0){
            cout << 0 << '\n';
            return;
        }
        sumc += c[i].second;
    }
    for(int i = 1; i <= n; i++){
        if(tr.get(1, 1, 1e18, 1, sumr + 1) < 0 || tr.get(1, 1, 1e18, 1, sumr + r[i].second) < 0){
            cout << 0 << '\n';
            return;
        }
        sumr += r[i].second;
    }
    cout << 1 << '\n';
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

    int t = 1;
    // cin >> t; 
    while(t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...