提出 #71340270

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <map>
using namespace std;
typedef long long ll;
const int maxn=(2e5)+10;
int n,q,a[maxn];
pair<int,int> b[maxn];
#define MP make_pair
int A[maxn],B[maxn];
int tr[maxn],cnt[maxn];
void add(int x) {
    for (;x<=n;x+=x&(-x)) tr[x]++;
}
int query(int x) {
    int res=0;
    for (;x;x-=x&(-x)) res+=tr[x];
    return res;
}
ll preA[maxn],preB[maxn];
pair<int,int> ans[maxn];
vector<int> pos[maxn];
vector<pair<int,int> > Q1[maxn],Q2[maxn];
void solve(vector<pair<int,int> > *Q,int flag) {
    for (int i=1;i<=n;i++) tr[i]=0,pos[i].clear();
    for (int i=n;i>=1;i--) {
        if (i<n) {
            add(a[i+1]);
            pos[a[i+1]].push_back(i+1);
        }
        for (pair<int,int> A : Q[i]) {
            int k=A.first,id=A.second;
            int l=1,r=n,mid,res=-1;
            while (l<=r) {
                mid=(l+r)>>1;
                if (query(mid)>=k) res=mid,r=mid-1;
                else l=mid+1;
            }
            k-=query(res-1);
            // if (id==5) printf("> %d %d %d\n",k,res,flag);
            res=pos[res][k-1];
            
            ans[id].second=res;
        }
    }
}
int main() {
    scanf("%d %d",&n,&q);
    for (int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        b[i]=MP(a[i],i);
    }
    sort(b+1,b+n+1);
    int fd=-1;
    for (int i=1;i<n;i++) if (b[i].first==b[i+1].first) { fd=i; break; }
    for (int i=n;i>=1;i--) {
        A[i]=query(a[i]-1);
        B[i]=n-i-cnt[a[i]]-A[i];
        cnt[a[i]]++,add(a[i]);
    }
    for (int i=1;i<=n;i++) preA[i]=preA[i-1]+A[i],preB[i]=preB[i-1]+B[i];
    ll tot=(ll)n*(n-1)/2;
    for (int _=1;_<=q;_++) {
        ll k; scanf("%lld",&k);
        if (k<=preA[n]) {
            int l=lower_bound(preA+1,preA+n+1,k)-preA;
            k-=preA[l-1];
            ans[_].first=l;
            Q1[l].push_back(MP(k,_));
        } else if (k>=tot-preB[n]+1) {
            k=tot-k+1;
            int l=lower_bound(preB+1,preB+n+1,k)-preB;
            k-=preB[l-1];
            ans[_].first=l;
            Q2[l].push_back(MP(k,_));
        } else {
            assert(fd!=-1);
            ans[_]=MP(b[fd].second,b[fd+1].second);
        }
    }
    solve(Q1,1);
    for (int i=1;i<=n;i++) a[i]=n-a[i]+1;
    solve(Q2,-1);
    for (int i=1;i<=q;i++) printf("%d %d\n",ans[i].first,ans[i].second);

    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function 'void solve(std::vector<std::pair<int, int> >*, int)':
./Main.cpp:23:42: warning: unused parameter 'flag' [-Wunused-parameter]
   23 | void solve(vector<pair<int,int> > *Q,int flag) {
      |                                      ~~~~^~~~

ジャッジ結果