Submission #1279689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279689		Ludissey	Event Hopping (BOI22_events)	C++20	10 / 100	72 ms	14372 KiB

events

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

const int LOG=24;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,q; cin >> n >> q;
    vector<pair<int,int>> a(n);
    vector<int> e(n);
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second, e[i]=i;;
    sort(all(e),[&](int _a, int b){
        if(a[_a].second==a[b].second) return a[_a].first<a[b].first;
        return a[_a].second<a[b].second;
    });
    vector<pair<int,int>> qrs(q);
    vector<int> ans(q,-1);
    vector<vector<pair<int,int>>> tans(n);
    for (int i = 0; i < q; i++) cin >> qrs[i].first >> qrs[i].second, tans[qrs[i].second-1].push_back({qrs[i].first-1, i});
    vector<int> indx;
    vector<int> l;
    vector<int> dis;
    for (int i = 0; i < n; i++)
    {
        while((sz(indx)>=1&&a[indx.back()].first>=a[e[i]].first)||(sz(indx)>=2&&a[indx[sz(indx)-2]].second>=a[e[i]].first)){
            indx.pop_back();
            l.pop_back();
            dis.pop_back();
        }
        if(sz(dis)) dis.push_back(dis.back()+(a[indx.back()].second<a[e[i]].first));
        else dis.push_back(0);
        l.push_back(a[e[i]].first);
        indx.push_back(e[i]);
        for (auto u : tans[e[i]])
        {
            int s=u.first;
            if(a[s].second>a[e[i]].second) continue;
            int up=upper_bound(all(l),a[s].second)-l.begin();
            if(up==0) continue;
            up--;
            if(dis[up]!=dis.back()) continue;
            ans[u.second]=1+((sz(dis)-1)-up);
            if(s==e[i]) ans[u.second]=0;
        }
        if(sz(indx)>=2&&a[indx[sz(indx)-2]].second==a[indx[sz(indx)-1]].second){
            indx.pop_back();
            l.pop_back();
            dis.pop_back();
        }
    }
    for (int i = 0; i < sz(ans); i++)
    {
        if(ans[i]==-1) cout << "impossible\n";
        else cout << ans[i] << "\n";
    }
    
    return 0;
}

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