제출 #526746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526746		joelau	Osumnjičeni (COCI21_osumnjiceni)	C++14	10 / 110	1038 ms	44804 KiB

Main

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

int N,Q;
pair<int,int> lst[200005];
vector<int> A;

struct node {
    int s,e,m,v,lazy; node *l, *r;
    node (int S, int E) {
        s = S, e = E, m = (s+e)/2, v = 0, lazy = -1;
        if (s != e) l = new node(s,m), r = new node(m+1,e);
    }
    void propo() {
        if (lazy == -1) return;
        v = lazy * (e-s+1);
        if (s != e) l->lazy = lazy, r->lazy = lazy;
        lazy = -1;
    }
    void update (int x, int y, int nv) {
        propo();
        if (s == x && e == y) lazy = nv;
        else {
            if (y <= m) l -> update(x,y,nv);
            else if (x > m) r -> update(x,y,nv);
            else l -> update(x,m,nv), r -> update(m+1,y,nv);
            l->propo(), r->propo();
            v = l->v + r->v;
        }
    }
    int query (int x, int y) {
        propo();
        if (s == x && e == y) return v;
        else if (y <= m) return l -> query(x,y);
        else if (x > m) return r -> query(x,y);
        else return l->query(x,m) + r->query(m+1,y);
    }
}*root;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> lst[i].first >> lst[i].second;
        A.push_back(lst[i].first); A.push_back(lst[i].second);
    }
    sort(A.begin(),A.end());
    A.resize(unique(A.begin(),A.end())-A.begin());
    for (int i = 0; i < N; ++i) {
        lst[i].first = lower_bound(A.begin(),A.end(),lst[i].first) - A.begin();
        lst[i].second = lower_bound(A.begin(),A.end(),lst[i].second) - A.begin();
    }
    root = new node(0,A.size()-1);
    cin >> Q;
    while (Q--) {
        int l,r; cin >> l >> r; l--, r--;
        root -> update(0,A.size()-1,0);
        int ans = 1;
        for (int i = l; i <= r; ++i) {
            if (root -> query(lst[i].first,lst[i].second) != 0) {
                ans++;
                root -> update(0,A.size()-1,0);
            }
            root -> update(lst[i].first,lst[i].second,1);
        }
        cout << ans << '\n';
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50