Submission #1117363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117363		Tai_xiu	Index (COCI21_index)	C++14	110 / 110	1279 ms	193076 KiB

index

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
const Z maxn=200005;
struct node
{
    Z l,r,val;
    node(){}
    node(Z _val,Z _l,Z _r){
    l=_l,r=_r,val=_val;}
}t[40*maxn];
Z n,q;
Z a[maxn],version[maxn];
Z cnode=0;
Z update(Z v,Z tl,Z tr,Z pos,Z nv)
{
    if (tl==tr){
        t[++cnode]=node(nv,0,0);
        return cnode;
    }
    Z curr=++cnode;
    Z tm=tl+tr>>1;
    if (pos<=tm){
        t[curr].l=update(t[v].l,tl,tm,pos,nv);
        t[curr].r=t[v].r;
    }
    else{
        t[curr].l=t[v].l;
        t[curr].r=update(t[v].r,tm+1,tr,pos,nv);
    }
    t[curr].val=t[t[curr].l].val+t[t[curr].r].val;
    return curr;
}
Z query(Z v,Z tl,Z tr,Z l,Z r)
{
    if (tl>tr || l>r || tl>r || tr<l) return 0;
    if (tl>=l && tr<=r) return t[v].val;
    Z tm=tl+tr>>1;
    return query(t[v].l,tl,tm,l,r)+query(t[v].r,tm+1,tr,l,r);
}
vi g[maxn];
void solve()
{
    cin>>n>>q;
    Z ma=0;
    FOR(i,1,n){ cin>>a[i]; ma=max(ma,a[i]);}
    FOR(i,1,n) g[a[i]+1].pb(i);
    FOR(i,1,n) version[1]=update(version[1],1,n,i,1);
  //  FOR(i,1,ma) cout<<version[i]<<" "<<'?'<<'\n';
    FOR(i,2,ma+1){
        version[i]=version[i-1];
        for (Z v:g[i]) version[i]=update(version[i],1,n,v,0);
    }
    while (q--){
        Z l,r;
        cin>>l>>r;
        Z l1=1,r1=ma;
        while (l1<=r1){
            Z mid=l1+r1>>1;
            if (query(version[mid],1,n,l,r)>=mid) l1=mid+1;
            else r1=mid-1;
        }
        cout<<l1-1<<'\n';
    }
  //  FOR(i,2,ma+1) cout<<query(version[i],1,n,1,n)<<'\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Z t=1;
  //  cin>>t;
    while(t--) solve();
}

Compilation message (stderr)

index.cpp: In function 'long long int update(long long int, long long int, long long int, long long int, long long int)':
index.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     Z tm=tl+tr>>1;
      |          ~~^~~
index.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
index.cpp:63:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     Z tm=tl+tr>>1;
      |          ~~^~~
index.cpp: In function 'void solve()':
index.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |             Z mid=l1+r1>>1;
      |                   ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50