Submission #1246344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246344		ErJ	Event Hopping (BOI22_events)	C++20	10 / 100	1597 ms	589824 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vi vector<ll>
#define pp pair<ll, ll>
#define vp vector<pp>
#define vpp vector<pair<ll, pp>>
#define inf 1000000000

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();

    ll n, q;
    cin >> n >> q;
    vp seg(n);
    vpp points;
    for(int i = 0; i < n; i++){
        cin >> seg[i].first >> seg[i].second;
        points.push_back({seg[i].first, {0, i}});
        points.push_back({seg[i].second, {1, i}});
    }
    sort(points.begin(), points.end());
    //sort(seg.begin(), seg.end());
    set<pp> sp;


    vector<vector<pair<ll, pp>>> queries(n); //kam, ans, ktera
    for(int i = 0; i < q; i++){
        ll ans = 0;
        ll start, end;
        cin >> start >> end;
        start--; end--;
        queries[start].push_back({end, {0, i}});
    }
    vp ans;
    sp.clear();
    set<ll> numSeg;
    vi rem;
    for(int i = 0; i < points.size(); i++){
        if(points[i].second.first == 0){
            ll aktseg = points[i].second.second;
            sp.insert({seg[aktseg].second, aktseg});
            numSeg.insert(aktseg);
        }else{
            ll aktseg = points[i].second.second;
            for(int j = 0; j < queries[aktseg].size(); j++){
                pair<ll, pp> query = queries[aktseg][j];
                if(query.first == aktseg){
                    ans.push_back({query.second.second, query.second.first});
                    continue;
                }
                if(numSeg.count(query.first)){
                    ans.push_back({query.second.second, query.second.first + 1});
                    continue;
                }
                ll to = seg[query.first].second;
                auto au = sp.lower_bound({to, inf});
                if(au == sp.begin() || sp.size() == 0){
                    ans.push_back({query.second.second, inf});
                    continue;
                }
                au--;
                pp nxt = *au;
                if(nxt.second == aktseg){
                    ans.push_back({query.second.second, inf});
                    continue;
                }

                queries[nxt.second].push_back({query.first, {query.second.first + 1, query.second.second}});
            }
            sp.erase({seg[aktseg].second, aktseg});
            rem.push_back(aktseg);
            if(i + 1 < points.size() && points[i + 1].first > points[i].first){
                for(ll remIt : rem){
                    numSeg.erase(remIt);
                }
            }
        }
    }
    vi ANS(q);
    for(int i = 0; i < ans.size(); i++){
        ANS[ans[i].first] = ans[i].second;
    }
    for(int i = 0; i < ANS.size(); i++){
        if(ANS[i] >= inf){
            cout << "impossible" << '\n';
        }else{
            cout << ANS[i] << '\n';
        }
    }
}

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