Submission #579659

#	Time	Username	Problem	Language	Result	Execution time	Memory
579659		wdjpng	Event Hopping (BOI22_events)	C++17	0 / 100	246 ms	524288 KiB

events

#include <bits/stdc++.h>


#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >=0; i--)
#define all(a) a.begin(), a.end()
#define pii pair<int,int>

using namespace std;

vector<pii>T(3e5,{1e15,-1});
pii update(int i, int l, int r, int ui, pii uv)
{
    if(r<=ui||l>ui) return T[i];
    if(l+1==r) return T[i]=min(T[i],uv);

    return T[i] = min(update(2*i,l,(l+r)/2,ui,uv),update(2*i+1,(l+r)/2,r,ui,uv));
}

pii query(int i, int l, int r, int ql, int qr)
{
    if(qr<=l||r<=ql) return {1e15,-1};
    if(l>=ql&&r<=qr) return T[i];
    return min(query(2*i,l,(l+r)/2,ql,qr),query(2*i+1,(l+r)/2,r,ql,qr));
}

struct ev {int s,e;};
bool path(ev a, ev b)
{
    return b.s<=a.e&&b.e>=a.e;
}

signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    vector<int>(1e9,-1);
    int n,q;
    cin>>n>>q;
    vector<ev>evs(n);
    for(auto& e: evs) cin>>e.s>>e.e;
    vector<int>cords;
    for(ev e : evs) {cords.push_back(e.s); cords.push_back(e.e);}
    sort(all(cords));
    cords.erase(unique(all(cords)), cords.end());
    for(ev& e : evs) 
    {
        e.s=lower_bound(all(cords),e.s)-cords.begin();
        e.e=lower_bound(all(cords),e.e)-cords.begin();
    }

    vector<int>next(n);
    assert(false);
    rep(cq, q)
    {
        int s,e;
        cin>>s>>e;

    }
    // rep(i,n) update(1,0,cords.size(), evs[i].e, {evs[i].s,i});

    // vector<vector<int>>up(n, vector<int>(20));
    // rep(i,n)
    // {
    //     up[i][0]=query(1,0,cords.size(),evs[i].s,evs[i].e+1).second;
    //     if(up[i][0]==-1) up[i][0]=i;
    // }

    // for(int j = 1; j < 20; j++) rep(i,n) up[i][j]=up[up[i][j-1]][j-1];

    // rep(cq,q)
    // {
    //     int s,e;
    //     cin>>s>>e;
    //     s--; e--;

    //     int sum = 0;
    //     int v = e;
    //     for(int j = 19; j>=0;j--) if(evs[up[v][j]].s>evs[s].e) {v=up[v][j]; sum+=1<<j;}
    //     if(evs[v].s>evs[s].e) {sum++; v=up[v][0];}
    //     if(!path(evs[s], evs[v])) cout<<"impossible\n";
    //     else {
    //         if(s!=v) sum++;
    //         cout<<sum<<'\n';
    //     }
    // }
}

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