重点班

C++14(g++5.4) 解法, 执行用时: 753ms, 内存消耗: 17120K, 提交时间: 2020-01-17 22:15:59

#include <iostream>
#include <algorithm>
#include <vector>
constexpr int N = 100'000, M = 1 << 18;
int n;
int t[M], min[M], ans[N], pm[N], a[N], b[N], bp[N];
std::vector<int> change[N], y;
void add(int p, int v) {
    min[p] += v;
    t[p] += v;
}
void push(int p) {
    add(2 * p, t[p]);
    add(2 * p + 1, t[p]);
    t[p] = 0;
}
void rangeAdd(int p, int l, int r, int x, int y, int v) {
    if (l >= y || r <= x)
        return;
    if (l >= x && r <= y)
        return add(p, v);
    int m = (l + r) / 2;
    push(p);
    rangeAdd(2 * p, l, m, x, y, v);
    rangeAdd(2 * p + 1, m, r, x, y, v);
    min[p] = std::min(min[2 * p], min[2 * p + 1]);
}
void search(int p, int l, int r, int x) {
    if (min[p] >= 0)
        return;
    if (r - l == 1) {
        ans[pm[l]] = x;
        y.push_back(l);
        min[p] = 1'000'000'000;
        return;
    }
    int m = (l + r) / 2;
    push(p);
    search(2 * p, l, m, x);
    search(2 * p + 1, m, r, x);
    min[p] = std::min(min[2 * p], min[2 * p + 1]);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i] >> b[i];
    for (int i = 0; i < n; ++i)
        pm[i] = i;
    std::sort(pm, pm + n, [&](int i, int j) {
        return b[i] < b[j];
    });
    for (int i = 0; i < n; ++i)
        bp[i] = b[pm[i]];
    for (int i = 0; i < n; ++i) {
        rangeAdd(1, 0, n, std::upper_bound(bp, bp + n, b[i]) - bp, n, 1);
        rangeAdd(1, 0, n, i, i + 1, -((n - 1 + a[pm[i]] - 1) / a[pm[i]]));
        if (a[pm[i]] == 1)
            continue;
        for (int j = 1; j < n; j += a[pm[i]])
            change[j].push_back(i);
    }
    int max = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (b[pm[i]] > max) {
            max = b[pm[i]];
            cnt = 1;
        } else if (b[pm[i]] == max) {
            ++cnt;
        }
    }
    if (cnt == 1)
        for (int i = 0; i < n; ++i)
            if (b[pm[i]] == max)
                rangeAdd(1, 0, n, i, i + 1, 1'000'000'000);
    int lastn = n, tt = 0;
    while (true) {
        search(1, 0, n, ++tt);
        if (y.empty())
            break;
        for (int i : y)
            rangeAdd(1, 0, n, std::upper_bound(bp, bp + n, b[pm[i]]) - bp, n, -1);
        for (int j = lastn - 1; j >= lastn - int(y.size()); --j)
            for (int i : change[j])
                rangeAdd(1, 0, n, i, i + 1, 1);
        lastn -= y.size();
        y.clear();
    }
    for (int i = 0; i < n; ++i)
        std::cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 322ms, 内存消耗: 19712K, 提交时间: 2020-01-17 21:01:08

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

template <typename T> void chmin(T&x,const T &y)
{
	if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
	if(x<y)x=y;
}
typedef int64_t s64;
typedef uint64_t u64;
typedef uint32_t u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
char readc()
{
	char c;
	while(gc<'-');
	return c;
}
int read()
{
	char c;
	while(gc<'-');
	if(c=='-')
	{
		int x=gc-'0';
		while(gc>='0')x=x*10+c-'0';
		return -x;
	}
	int x=c-'0';
	while(gc>='0')x=x*10+c-'0';
	return x;
}
#undef gc

const int N=1e5+5;
int n,a[N],b[N],c[N],s[N],q[N],ndy[N],dy[N],dy1[N],h[N];
int mn[N*3],ad[N*3],d,ans[N];
vector<int>lk[N];

void modify(int i,int x)
{
	i+=d;mn[i]=x;
	while(i>>=1)mn[i]=min(mn[i*2],mn[i*2+1])+ad[i];
}
void suf_add(int i,int w)
{
	if(i>n)return ;
	i+=d;mn[i]+=w;ad[i]+=w;
	while(i>1)
	{
		if(i%2==0){mn[i+1]+=w;ad[i+1]+=w;}
		i>>=1;
		mn[i]=min(mn[i*2],mn[i*2+1])+ad[i];
	}
}
int s0,s1,st[N];
void dfs(int i,int s)
{
	if(mn[i]+s>=0)return ;
	if(i>d)
	{
		//cerr<<i-d<<" "<<mn[i]+s<<endl;
		st[++s1]=ndy[i-d];
		return ;
	}
	rep(j,0,1)dfs(i*2+j,s+ad[i]);
}

int main()
{
#ifdef kcz
	freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
	n=read();
	rep(i,1,n){a[i]=read();b[i]=read();}
	rep(i,1,n)q[i]=b[i];
	sort(q+1,q+n+1);
	rep(i,1,n)
	{
		dy[i]=lower_bound(q+1,q+n+1,b[i])-q;
		dy1[i]=lower_bound(q+1,q+n+1,b[i]+1)-q;
		dy[i]+=h[dy[i]]++;
		ndy[dy[i]]=i;
	}
	for(d=1;d<n;d<<=1);d-=1;
	rep(i,1,n)modify(dy[i],-(n-1+a[i]-1)/a[i]);
	rep(i,1,n)
	{
		suf_add(dy1[i],1);
		for(int j=1;j<n;j+=a[i])lk[j].push_back(i);
	}
	rep(i,n+1,d+1)modify(i,1e9);
	//cerr<<mn[d+1]<<endl;
	while(mn[1]<0)
	{
		++s0;
		int s1_0=s1;
		dfs(1,0);
		rep(i,s1_0+1,s1)
		{
			int x=st[i];
			//cerr<<x<<endl;
			ans[x]=s0;
			modify(dy[x],1e9);
			suf_add(dy1[x],-1);
			for(auto y:lk[n-i])
			if(!ans[y])modify(dy[y],mn[dy[y]+d]+1);
		}
	}
	rep(i,1,n)printf("%d ",ans[i]);
}

详情