Submission #1304706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304706		Sofiatpc	Event Hopping (BOI22_events)	C++20	10 / 100	60 ms	11760 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define fi first
#define sc second
struct intervalo{
    int s,e,id;
    bool operator <(intervalo b){
        if(e == b.e)return s < b.s;
        return e < b.e;
    }
};
const int MAXN = 1e5+5, INF = 1e9+5;
pair<int,int> ini[MAXN];
vector< pair<int,int> > que[MAXN];
intervalo a[MAXN];
int ans[MAXN];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n,q; cin>>n>>q;
    for(int i = 1; i <= n; i++){
        cin>>ini[i].fi>>ini[i].sc;
        a[i].s = ini[i].fi; a[i].e = ini[i].sc; a[i].id = i;
    }
    sort(a+1,a+1+n);

    for(int i = 1; i <= q; i++){
        int s,e; cin>>s>>e;
        que[e].push_back({s,i});
    }

    vector<  vector<pair<int,int>> > v; v.push_back({});
    for(int i = 1; i <= n; i++){
        while(1){
            while(sz(v.back()) > 0 && v.back().back().fi >= a[i].s)v.back().pop_back();
            if(sz(v.back()) != 0 || sz(v) == 1)break;
            v.pop_back();
        }

        if(sz(v.back()) != 0 && v.back().back().sc < a[i].s)v.push_back({});
        
        while(sz(v.back()) > 1 && v.back()[sz(v.back())-2].sc >= a[i].s)v.back().pop_back();

        v.back().push_back({a[i].s, a[i].e});

        int eid = a[i].id;
        for(int j = 0; j < sz(que[eid]); j++){
            int sid = que[eid][j].fi, ss = ini[sid].fi, se = ini[sid].sc;

            if(sid == eid) ans[ que[eid][j].sc ] = 0;
            else if(v.back()[0].fi > se)ans[ que[eid][j].sc ] = -1;
            else{
                int x = upper_bound(v.back().begin(),v.back().end(), make_pair(se,INF))-v.back().begin(); x--;
                if(x >= 0 && v.back()[x].fi <= se && se <= v.back()[x].sc) ans[ que[eid][j].sc ] = sz(v.back())-x;
                else ans[ que[eid][j].sc ] = -1; 
            }
        }
    }

    for(int i = 1; i <= q; i++){
        if(ans[i] == -1)cout<<"impossible\n";
        else cout<<ans[i]<<"\n";
    }
}   

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