Submission #751396

#	Time	Username	Problem	Language	Result	Execution time	Memory
751396		bgnbvnbv	Osumnjičeni (COCI21_osumnjiceni)	C++14	110 / 110	729 ms	101548 KiB

Main

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
struct Tinter
{
    ll l,r,id;
    bool operator<(const Tinter&o)
    {
        return l<o.l;
    }
}e[maxN];
ll lazy[8*maxN],st[8*maxN];
void down(ll id)
{
    ll &x=lazy[id];
    if(x!=-1)
    {
        st[id*2]=x;
        lazy[id*2]=x;
        st[id*2+1]=x;
        lazy[id*2+1]=x;
        x=-1;
    }
}
ll n;
void update(ll i,ll j,ll val,ll id=1,ll l=1,ll r=2*n)
{
    if(j<l||r<i) return;
    if(i<=l&&r<=j)
    {
        st[id]=val;
        lazy[id]=val;
        return;
    }
    ll mid=l+r>>1;
    down(id);
    update(i,j,val,id*2,l,mid);
    update(i,j,val,id*2+1,mid+1,r);
    st[id]=min(st[id*2],st[id*2+1]);
}
ll get(ll i,ll j,ll id=1,ll l=1,ll r=2*n)
{
    if(j<l||r<i) return n+1;
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    down(id);
    return min(get(i,j,id*2,l,mid),get(i,j,id*2+1,mid+1,r));
}
ll r[maxN];
ll mn[maxN][19],nxt[maxN][19];
int log(ll x)
{
    return 64 - __builtin_clzll(x) - 1;
}
ll g(ll i,ll j)
{
    ll k=j-i+1;
    k=log(k);
    return min(mn[i][k],mn[j-(1<<k)+1][k]);
}
void solve()
{
    vector<ll>vec;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> e[i].l >> e[i].r;
        vec.pb(e[i].l);
        vec.pb(e[i].r);
        e[i].id=i;
        r[i]=n+1;
    }
    sort(vec.begin(),vec.end());
    for(int i=1;i<=n;i++)
    {
        e[i].l=lower_bound(vec.begin(),vec.end(),e[i].l)-vec.begin()+1;
        e[i].r=lower_bound(vec.begin(),vec.end(),e[i].r)-vec.begin()+1;
    }
    fill(st,st+8*maxN,n+1);
    fill(lazy,lazy+8*maxN,-1);
    for(int i=n;i>=1;i--)
    {
        r[i]=min(r[i],get(e[i].l,e[i].r));
        update(e[i].l,e[i].r,i);
        mn[i][0]=r[i];
        //cout << r[i]<<' ';
    }
    for(int j=1;j<=18;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(i+(1<<j)-1>n) break;
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        ll low=i,high=n;
        while(low<=high)
        {
            ll mid=low+high>>1;
            if(g(i,mid)>mid) low=mid+1;
            else high=mid-1;
        }
        nxt[i][0]=low;
    }
    //cout << '\n';
    nxt[n+1][0]=n+1;
    for(int j=1;j<=18;j++)
    {
        for(int i=1;i<=n+1;i++)
        {
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
        }
    }
    ll q;
    cin >> q;
    while(q--)
    {
        ll a,b;
        cin >> a >> b;
        ll ans=1;
        for(int j=18;j>=0;j--)
        {
            if(nxt[a][j]<=b)
            {
                a=nxt[a][j];
                ans+=1<<j;
            }
        }
        cout << ans<<'\n';

    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
Main.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     ll mid=l+r>>1;
      |            ~^~
Main.cpp: In function 'll get(ll, ll, ll, ll, ll)':
Main.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     ll mid=l+r>>1;
      |            ~^~
Main.cpp: In function 'void solve()':
Main.cpp:110:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |             ll mid=low+high>>1;
      |                    ~~~^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50