Submission #886189

#	Time	Username	Problem	Language	Result	Execution time	Memory
886189		vjudge1	Curtains (NOI23_curtains)	C++17	20 / 100	864 ms	72528 KiB

curtains

#include <bits/stdc++.h>

#define int long long int
#define MP make_pair
#define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)
#define pb push_back

const int N = 5e5+5;
const int M = 5e5 + 5;
const int MOD = 1e9+7;
const int INF = 1e17;
using namespace std;

void fastio() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
}
int n,m,q;
struct Query {
    int l, r, id;
    Query() : l(0), r(0), id(0) {};
    Query(int lf, int rg, int i) : l(lf), r(rg), id(i) {};
    void input(int ind) {
        id = ind;
        cin>>l>>r;
    }

    const bool operator<(const Query &oth) {
        return r < oth.r;
    }
};

struct Node {
    int cnt, mn, lazy;
    Node() : cnt(0), mn(INF), lazy(0) {};
    Node(int c, int m) : cnt(c), mn(m), lazy(0) {};
    Node comb(Node &x) {
        if(x.mn == mn) return Node(cnt + x.cnt, mn);
        if(x.mn > mn) return Node(cnt, mn);
        return Node(x.cnt, x.mn);
    }   
};
struct SegTree {
    vector<Node> data;
    int sz;

    void build(int tl, int tr, int v) {
        if(tl == tr) {
            data[v] = Node(1,0);
            return;
        }
        int tm = (tl + tr) >> 1;
        build(tl, tm, v*2);
        build(tm + 1, tr, v*2+1);
        data[v] = data[v*2].comb(data[v*2+1]);
    }

    SegTree(int sz) {
        this->sz = sz;
        data.assign(4*(sz + 5), Node());
        build(1, sz, 1);
    }
    void push(int v) {
        data[v*2].lazy += data[v].lazy;
        data[v*2].mn += data[v].lazy;
        data[v*2+1].lazy += data[v].lazy;
        data[v*2+1].mn += data[v].lazy;
        data[v].lazy = 0;
           
    }
    
    void update(int tl, int tr, int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            data[v].mn += val;
            data[v].lazy += val;
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        update(tl, tm, v*2, l, r, val);
        update(tm + 1, tr, v*2+1, l, r, val);
        data[v] = data[v*2].comb(data[v*2+1]);

    }
    void update(int l, int r, int val) {
        update(1, sz, 1, l, r, val);
    }
    int query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            if(data[v].mn == 0) {
                return data[v].cnt;
            }
            return 0;
        }
        if(tl > r || tr < l) {
            return 0;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        return query(tl, tm, v*2, l, r) + query(tm + 1, tr, v*2+1, l, r);
    } 
    int query(int l, int r) {
        return query(1, sz, 1, l, r);
    }

};

vector<Query> curt; // l, r
vector<Query> quer;
vector<bool> res(N, 0);
void solve() {
    cin>>n>>m>>q;
    curt.resize(m);
    quer.resize(q);
    REP(i,m) {
        curt[i].input(i + 1);
    }
    REP(i,q) {
        quer[i].input(i + 1);
    }
    sort(quer.begin(), quer.end());
    sort(curt.begin(), curt.end());
    
    SegTree st(n);
    int ind = 0;

    
    for(int i = 0; i<q; i++) {
        while(ind < m && curt[ind].r <= quer[i].r) {
            st.update(curt[ind].l, curt[ind].r, 1);
            ind++;
        }
        int cnt = st.query(1, quer[i].r);
        // cout<<"cnt:"<<cnt<<"id:"<<quer[i].id<<"\n";
        res[quer[i].id] = (cnt == 0);
        
    }
    
    for(int i = 1; i<=q; i++) {
        // cout<<res[i]<<" wtf\n";
        if(res[i]) cout<<"YES";
        else cout<<"NO";
        cout<<"\n";
    }
}

signed main() {
    // fastio();
    solve();
}   

Compilation message (stderr)

curtains.cpp: In function 'void solve()':
curtains.cpp:5:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)
      |                          ^
curtains.cpp:118:5: note: in expansion of macro 'REP'
  118 |     REP(i,m) {
      |     ^~~
curtains.cpp:5:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)
      |                          ^
curtains.cpp:121:5: note: in expansion of macro 'REP'
  121 |     REP(i,q) {
      |     ^~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20