Submission #1311040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311040		HoriaHaivas	Event Hopping (BOI22_events)	C++20	30 / 100	241 ms	38660 KiB

events

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}


struct Node
{
    int minval;
    int minpoz;
};

int s[100005];
int e[100005];
int up[17][100005];//binary lifting pe predecesorii optimi
vector<int> vals;
map<int,int> normie;
int weat;


class AINT
{
public:
    Node aint[800005];

    Node combine(Node a, Node b)
    {
        Node c;
        if (a.minval<b.minval)
            c=a;
        else if (b.minval<a.minval)
            c=b;
        else
        {
            c.minval=a.minval;
            c.minpoz=min(a.minpoz,b.minpoz);
        }
        return c;
    }

    void build(int l, int r, int val)
    {
        if (l==r)
        {
            aint[val].minval=1e9;
            aint[val].minpoz=0;
            return;
        }
        int mid;
        mid=(l+r)/2;
        build(l,mid,val*2);
        build(mid+1,r,val*2+1);
        aint[val]=combine(aint[val*2],aint[val*2+1]);
    }

    void update(int l, int r, int val, int poz, int x, int truepoz)
    {
        if (l==r && l==poz)
        {
            aint[val]=combine(aint[val],{x,truepoz});
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (poz<=mid)
            update(l,mid,val*2,poz,x,truepoz);
        else
            update(mid+1,r,val*2+1,poz,x,truepoz);
        aint[val]=combine(aint[val*2],aint[val*2+1]);
    }

    Node query(int l, int r, int val, int qa, int qb)
    {
        if (qa<=l && r<=qb)
        {
            return aint[val];
        }
        int mid;
        Node ans= {1000000000,0};
        mid=(l+r)/2;
        if (qa<=mid)
            ans=combine(ans,query(l,mid,val*2,qa,qb));
        if (qb>mid)
            ans=combine(ans,query(mid+1,r,val*2+1,qa,qb));
        return ans;
    }
} sinistrel;


signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q,i,j,cnt,st,en,ans;
    Node res;
    cin >> n >> q;
    for (i=1; i<=n; i++)
    {
        cin >> s[i] >> e[i];
        vals.push_back(s[i]);
        vals.push_back(e[i]);
    }
    sort(vals.begin(),vals.end());
    cnt=0;
    for (i=0; i<vals.size(); i++)
    {
        if (i==0 || vals[i]!=vals[i-1])
            cnt++;
        normie[vals[i]]=cnt;
    }
    sinistrel.build(1,cnt,1);
    for (i=1; i<=n; i++)
    {
        s[i]=normie[s[i]];
        e[i]=normie[e[i]];
        sinistrel.update(1,cnt,1,e[i],s[i],i);
    }
    for (i=1; i<=n; i++)
    {
        weat=i;
        res=sinistrel.query(1,cnt,1,s[i],e[i]);
        if (res.minpoz==i)
        up[0][i]=0;
        else
        up[0][i]=res.minpoz;
    }
    for (i=1;i<=16;i++)
    {
         for (j=1;j<=n;j++)
         {
              up[i][j]=up[i-1][up[i-1][j]];
         }
    }
    for (i=1; i<=q; i++)
    {
        cin >> st >> en;
        if (st==en)
        {
            cout << "0\n";
            continue;
        }
        ans=0;
        for (j=16; j>=0; j--)
        {
            if (e[up[j][en]]>e[st])
            {
                en=up[j][en];
                ans+=(1<<j);
            }
        }
        if (s[en]<=e[st] && e[st]<=e[en])
            cout << ans+1 << "\n";
        else
            cout << "impossible\n";
    }
    return 0;
}

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