Submission #1054205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054205		shiocan	Joker (BOI20_joker)	C++17	0 / 100	188 ms	49684 KiB

Joker

#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
    #define cin fin
    #define cout fout
    string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/

#define ull unsigned long long 
#define ll long long
#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7; 
const int inf = 1e18;
const int N = 1e5 + 100;

vector<vector<int>> a;

struct segtree{
    struct item{
        int val = 0;
        int lazy = 0;
    };

    // const item DEFAULT = {0, 1, 0};

    vector<item> s;
    int size = 0;

    void apply(int x, int val){
        s[x].val += val;
        s[x].lazy += val;
    }
    
    void push(int x){
        if(s[x].lazy != 0){
            apply(2 * x + 1, s[x].lazy);
            apply(2 * x + 2, s[x].lazy);
            s[x].lazy = 0;
        }
    }

    void merge(int x){
        s[x].val = (s[2 * x + 1].val + s[2 * x + 2].val);
    }

    void build_tree(int x, int l, int r){
        if(l == r){
            s[x] = {0, 0};
            return;
        }

        int mid = (l + r) >> 1;

        build_tree(2 * x + 1, l, mid);
        build_tree(2 * x + 2, mid+1, r);
        merge(x);
    }

    void upd(int x, int lx, int rx, int l, int r, int val){
        if(l > r)
            return;

        if(lx == l && rx == r){
            apply(x, val);
            return;
        }

        push(x);

        int mid = (lx + rx) >> 1;

        upd(2 * x + 1, lx, mid, l, min(r, mid), val);
        upd(2 * x + 2, mid+1, rx, max(l, mid+1), r, val);
        
        merge(x);
    }

    void upd(int l, int r, int val){
        upd(0, 0, size-1, l, r, val);
    }

    int query(int x, int lx, int rx, int l, int r){
        if(l > r)
            return 0;
        if(l <= lx && rx <= r)
            return s[x].val;

        push(x);

        int mid = (lx + rx) >> 1;

        int s1 = query(2 * x + 1, lx, mid, l, min(r, mid));
        int s2 = query(2 * x + 2, mid+1, rx, max(l, mid+1), r);

        return (s1 + s2);
    }   
    int query(int l, int r){
        return query(0, 0, size-1, l, r);
    }

    segtree(int n){
        size = n;
        s.resize(4 * n);
        build_tree(0, 0, n-1);
    }
};

map<pii, int> mp;

void solve(){   
    int n, m, q;
    cin >> n >> m >> q;

    a = vector<vector<int>> (n);


    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;

        --x, --y;

        a[x].push_back(y);
        a[y].push_back(x);
        mp[{x, y}] = mp[{y, x}] = i;
    }

    segtree st(m + 2);

    auto ok = [&](){
        queue<int> q;
        q.push(0);

        vector<bool> vis(n, 0);
        while(!q.empty()){
            int s = q.front();
            q.pop();

            if(vis[s])
                return 1;

            vis[s] = 1;
            for(auto i : a[s])
                if(i != s){
                    int idx = mp[{i, s}];
                    if(st.query(idx, idx) == 0)
                        q.push(i);
                
                }
        }        
        

        return 0;
    };

    int l = 0, r = m + 1, mid;
    while(l < r - 1){
        mid = (l + r) >> 1;

        st.upd(0, mid - 1, -1);
        if(ok())
            l = mid;
        else
            r = mid;
        st.upd(0, mid - 1, 1);
    }

    // cout << r << '\n';

    while(q--){
        int x, y;
        cin >> x >> y;

        --x, --y;

        cout << (y >= r ? "YES" : "NO") << '\n';
    }
}      

int32_t main(){ 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29