Submission #593940

#	Time	Username	Problem	Language	Result	Execution time	Memory
593940		azberjibiou	Event Hopping (BOI22_events)	C++17	100 / 100	900 ms	13192 KiB

events

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=100010;
const int MOD=1e9+7;
int N, Q, M;
pii A[mxN];
vector <int> coor;
int sps[mxN][18];
int mins[mxN];
int ans[mxN];
pii rng[mxN];
pii qry[mxN];
void make_coor()
{
    for(int i=1;i<=N;i++)   coor.push_back(A[i].sec);
    sort(coor.begin(), coor.end());
    coor.erase(unique(coor.begin(), coor.end()), coor.end());
    for(int i=1;i<=N;i++)   A[i].fir=lower_bound(coor.begin(), coor.end(), A[i].fir)-coor.begin();
    for(int i=1;i<=N;i++)   A[i].sec=lower_bound(coor.begin(), coor.end(), A[i].sec)-coor.begin();
    M=coor.size();
}
int seg[4*mxN];
void init(int idx, int s, int e)
{
    if(s==e)
    {
        seg[idx]=mins[s];
        return;
    }
    int mid=(s+e)/2;
    init(2*idx, s, mid);
    init(2*idx+1, mid+1, e);
    seg[idx]=min(seg[2*idx], seg[2*idx+1]);
}
int solv(int idx, int s1, int e1, int s2, int e2)
{
    if(s2>e1 || s1>e2)  return M;
    if(s2<=s1 && e1<=e2)    return seg[idx];
    int mid=(s1+e1)/2;
    return min(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
}
int main()
{
    gibon
    cin >> N >> Q;
    for(int i=1;i<=N;i++)   cin >> A[i].fir >> A[i].sec;
    make_coor();
    for(int i=1;i<=N;i++)   sps[i][0]=A[i].fir;
    for(int i=1;i<18;i++)
    {
        for(int j=0;j<M;j++)    mins[j]=M;
        for(int j=1;j<=N;j++)   mins[A[j].sec]=min(mins[A[j].sec], sps[j][i-1]);
        init(1, 0, M-1);
        for(int j=1;j<=N;j++)   sps[j][i]=solv(1, 0, M-1, sps[j][i-1], A[j].sec);
    }
    for(int i=1;i<=Q;i++)   cin >> qry[i].fir >> qry[i].sec;
    for(int i=1;i<=Q;i++)   rng[i]=A[qry[i].sec];
    for(int i=16;i>=0;i--)
    {
        for(int j=0;j<M;j++)    mins[j]=M;
        for(int j=1;j<=N;j++)   mins[A[j].sec]=min(mins[A[j].sec], sps[j][i]);
        init(1, 0, M-1);
        for(int j=1;j<=Q;j++)
        {
            int res=solv(1, 0, M-1, rng[j].fir, rng[j].sec);
            if(res>A[qry[j].fir].sec)   ans[j]+=(1<<i), rng[j].fir=res;
        }
    }
    for(int i=1;i<=Q;i++)
    {
        if(sps[qry[i].sec][17]>A[qry[i].fir].sec || A[qry[i].sec].sec<A[qry[i].fir].sec)    cout << "impossible\n";
        else if(qry[i].sec==qry[i].fir) cout << "0\n";
        else if(A[qry[i].sec].fir<=A[qry[i].fir].sec)   cout << "1\n";
        else    cout << ans[i]+2 << '\n';
    }
}

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