oj.uz

Submission #1077526

# Submission time Handle Problem Language Result Execution time Memory
1077526 2024-08-27T07:52:13 Z LIF Event Hopping (BOI22_events) C++14
25 / 100
 1500 ms 18920 KB 
#include<bits/stdc++.h>
using namespace std;
int n,q,l[500005],r[500005],go[500005][30],pos[500005];
struct mn
{
    int val;
    int id;
}minn[800005];
struct nod
{
    int ll;
    int rr;
    int id;
}node[500005];
bool cmp(nod x,nod y)
{
   if(x.rr == y.rr)return x.ll < y.ll;
   else return x.rr < y.rr;
}
int read()
{
    int x=0,f=1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x<<3) + (x<<1) + (ch-'0');
        ch = getchar();
    }
    return x*f;
}
void pushup(int rt)
{
    if(minn[rt<<1].val < minn[rt<<1|1].val)
    {
        minn[rt].val = minn[rt<<1].val;
        minn[rt].id = minn[rt<<1].id;
    }
    else
    {
        minn[rt].val = minn[rt<<1|1].val;
        minn[rt].id = minn[rt<<1|1].id;
    }
    return;
}
pair<int,int> query(int l,int r,int queryl,int queryr,int rt)
{
    if(queryl <= l && r <= queryr)
    {
        return make_pair(minn[rt].val,minn[rt].id);
    }
    int mid = (l+r)>>1;
    pair<int,int> fir = make_pair(2e9,-1);
    if(mid >= queryl)
    {
        auto pp = query(l,mid,queryl,queryr,rt<<1);
        if(pp.first < fir.first)fir = pp;
    }
    if(mid + 1 <= queryr)
    {
        auto pp = query(mid+1,r,queryl,queryr,rt<<1|1);
        if(pp.first < fir.first)fir = pp;
    }
    return fir;
}
void build(int l,int r,int rt)
{
    if(l == r)
    {
        minn[rt].val = node[l].ll;
        minn[rt].id = l;
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
    return;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        l[i] = read();r[i] = read();
        nod temp = nod{l[i],r[i],i};
        node[i] = temp;
    }
    sort(node+1,node+n+1,cmp);
    build(1,n,1);
    for(int i=1;i<=n;i++)
    {
        go[i][0] = -1;
        int ll = 1,rr = i-1,last = -1;
        while (ll<=rr)
        {
            int mid = (ll+rr)>>1;
            if(node[mid].rr >= node[i].ll)
            {
                last = mid;
                rr = mid - 1;
            }
            else ll = mid + 1;
        }
        if(last <= 0)go[i][0] = -1;
        else
        {
            auto pp = query(1,n,last,i-1,1);
            go[i][0] = pp.second;
        }
    }
    for(int i=1;i<=n;i++)
    {
        pos[node[i].id] = i;
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=1;(j+(1<<i)-1)<=n;j++)
        {
            if(go[j][i-1] == -1)
            {
                go[j][i] = -1;
                continue;
            }
            go[j][i] = go[go[j][i-1]][i-1];
        }
    }
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<node[i].ll<<" "<<node[i].rr<<endl;
    // }
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<go[i][0]<<" ";
    // }
    // cout<<endl;
    // cout<<endl;
    while(q--)
    {
        int s,e;
        cin>>s>>e;
        if(e == s)
        {
            cout<<"0"<<endl;
            continue;
        }
        if(l[e] <= r[s] && r[s] <= r[e])
        {
            cout<<"1"<<endl;
            continue;
        }
        int now = pos[e];
        int ans = 0;
        bool can = true;
        for(int i=1;i<=n;i++)
        {
            int target = go[now][0];
            if(target == -1)continue;
            if(node[target].ll > r[s])
            {
                now = target;
                ans++;
            }
        }
        if(go[now][0] == -1)
        {
            can = false;
        }
        else
        {
            now = go[now][0];
            ans++;
        }
        //cout<<"last: "<<now<<endl;
        int ll = node[now].ll;
        int rr = node[now].rr;
        if(can == true && ll <= r[s] && r[s] <= rr)cout<<ans+1<<endl;
        else cout<<"impossible"<<endl;
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1587 ms 18920 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 496 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 456 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 496 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 500 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 500 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 991 ms 2644 KB Output is correct
20 Execution timed out 1557 ms 2640 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 496 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 444 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 75 ms 18440 KB Output is correct
20 Correct 50 ms 17744 KB Output is correct
21 Correct 53 ms 18256 KB Output is correct
22 Correct 46 ms 18516 KB Output is correct
23 Correct 40 ms 18512 KB Output is correct
24 Correct 51 ms 18536 KB Output is correct
25 Correct 30 ms 17744 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1517 ms 18756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1587 ms 18920 KB Time limit exceeded
3 Halted 0 ms 0 KB -