Submission #1178112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178112		tdkhai	Index (COCI21_index)	C++20	110 / 110	340 ms	19036 KiB

index

/*
K stands for "Khongbietcode"
grade 11 computer science
Tran Dai Nghia Highschool for the gifted
*/
#include<bits/stdc++.h>
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define pb push_back
#define ull unsigned long long
#define llll pair<ll,ll>
#define llllm map<ll,ll>
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/gcd(a,b)
#define X first
#define Y second
#define INF 1LL<<60

using namespace std;

const int N=2e5+5;
int n,q,a[N],ft[N],l[N],r[N],L[N],R[N],question[N],ans[N],cur[N];
vector<pair<int,int>> query[N];
bool asked[N];
void update(int u)
{
    while(u)
    {
        ft[u]++;
        u-=u&(-u);
    }
}
int get(int u)
{
    int ret=0;
    while(u<=2e5)
    {
        ret+=ft[u];
        u+=u&(-u);
    }
    return ret;
}
void solve(){
    cin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for(int i=1;i<=q;i++)
    {
        cin >> L[i] >> R[i];
        query[L[i]-1].push_back({i,-1});
        query[R[i]].push_back({i,1});
        l[i]=1;r[i]=R[i]-L[i]+1;
        ans[i]=1;
    }

    while(true)
    {
        bool check=false;
        for(int i=1;i<=q;i++)
        {
            asked[i]=false;
            cur[i]=0;
            if(l[i]<=r[i])
            {
                check=true;
                asked[i]=true;
                int mid=(l[i]+r[i])/2;
                question[i]=mid;
            }
        }
        if(!check) break;
        for(int i=1;i<=n;i++)
        {
            update(a[i]);
            for(int j=0;j<query[i].size();j++)
            {
                int id=query[i][j].first,delta=query[i][j].second;
                if(!asked[id]) continue;
                cur[id]+=delta*get(question[id]);
                if(delta==1)
                {
                    if(cur[id]>=question[id])
                    {
                        ans[id]=question[id];
                        l[id]=question[id]+1;
                    }
                    else
                    {
                        r[id]=question[id]-1;
                    }
                }
            }
        }
        memset(ft,0,sizeof(ft));
    }
    for(int i=1;i<=q;i++)
    {
        cout << ans[i] << '\n';
    }
}
int main(){
    fastIO;
    //freopen("tdk.inp","r",stdin);
    //freopen("tdk.out","w",stdout);
    //freopen("tdk.err","b",stderr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout << endl;
    }
    // cout << "\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
    return 0;
}

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