Submission #1284218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284218		quan606303	Index (COCI21_index)	C++20	110 / 110	442 ms	24988 KiB

index

///0-0 : what is your motivation, quan606303?
///quan606303 : Hutao
/*idea : 



*/
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int maxn=200005;
int BIT[maxn];
int n,q;
pair<int,int> a[maxn];
void upd(int x,int cnt)
{
    for (;x<maxn;x+=(x&-x))BIT[x]+=cnt;
}
int get(int x)
{
    int sum=0;
    for (;x>0;x&=(x-1))sum+=BIT[x];
    return sum;
}
int get_range(int l,int r)
{
    return get(r)-get(l-1);
}
int l[maxn],r[maxn],ans[maxn];
pair<int,int> b[maxn];
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i].fi;
        a[i].se=i;
    }
    sort(a+1,a+1+n);
    for (int i=1;i<=q;i++)
    {
        cin>>b[i].fi>>b[i].se;
        l[i]=1;
        r[i]=n;
        ans[i]=0;
    }
    vector<vector<int> > queries;
    bool process=true;
    while (process)
    {
        process=false;
        queries.assign(n+5,vector<int>());
        for (int i=1;i<=q;i++)
        {
            if (l[i]>r[i])continue;
            process=true;
            int mid=(l[i]+r[i])/2;
            queries[mid].push_back(i);
        }
        vector<int> vt;
        for (int mid=n,i=n;mid>=1;mid--)
        {
            while (i>=1&&a[i].fi>=mid)
            {
                upd(a[i].se,1);
                vt.push_back(a[i].se);
                i--;
            }
            int cnt=get_range(b[mid].fi,b[mid].se);
            for (auto c:queries[mid])
            {
                int cnt=get_range(b[c].fi,b[c].se);
                if (cnt>=mid)
                {
                    l[c]=mid+1;
                    ans[c]=mid;
                }
                else r[c]=mid-1;
            }
        }
        for (auto i:vt)upd(i,-1);
        queries.clear();
    }
    for (int i=1;i<=q;i++)cout<<ans[i]<<endl;
    return 0;
}

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