C++14(g++5.4) 解法, 执行用时: 465ms, 内存消耗: 11624K, 提交时间: 2020-05-28 21:05:03

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

typedef long long ll;
const int maxn = 5e5 + 5;
int ind[maxn], num[maxn], ans[maxn];

int n, sum[maxn];
void Update(int i) {
    while(i <= n) {
        sum[i]++;
        i += i&(-i);
    }
}
int Query(int x) {
    int i = 0, j = 19;
    while(~j) {
        if((i|1<<j) <= n && (i|1<<j)-sum[i|1<<j] < x) {
            i |= 1<<j;
            x += sum[i];
        }
        j--;
    }
    return i+1;
}

int main() {

    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", ind+i, num+i);

    for(int i = n; i; i--) {
        int k = Query(ind[i]);
        ans[k] = num[i];
        Update(k);
    }

    printf("%d", ans[1]);
    for(int i = 2; i <= n; i++) printf(" %d", ans[i]);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 642ms, 内存消耗: 18016K, 提交时间: 2020-06-29 21:49:31

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

int i,j,n,a[500005],id[500005],S[500005]={0},ans[500005];
int lowbit(int x)
{
	return x&(-x);
}
void update(int i,int x)
{
	while(i<=n)S[i]+=x,i+=lowbit(i);
}
int getsum(int i)
{
	int s=0;
	while(i)s+=S[i],i-=lowbit(i);
	return s;
}
int find(int x)
{
    int l=1,r=n,mid,ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(mid-getsum(mid)<x)l=mid+1;
        else ans=mid,r=mid-1;
    }
    return ans;
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d%d",&id[i],&a[i]);
	for(i=n;i>=1;i--)j=find(id[i]),ans[j]=a[i],update(j,1);
	for(i=1;i<=n;i++)printf("%d ",ans[i]);
}