C++14(g++5.4) 解法, 执行用时: 96ms, 内存消耗: 21348K, 提交时间: 2019-10-29 22:17:36

// luogu-judger-enable-o2
// luogu-judger-enable-o2
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n,k,tot=0;
int id[N],t[N],sum[N],cnt[N];

struct node { int l,r,val; } w[N<<2]; 
struct Queue {
    int h,t,len;
    inline bool empty() { return !len; }
    inline void push_back(int x) {
        if (len) w[++tot]=(node){t,0,x},w[t].r=tot,t=w[t].r;
        else w[++tot]=(node){0,0,x},h=t=tot;
        ++len;
    }
    inline void pop_back() { t=w[t].l,--len; }
    inline void pop_front() { h=w[h].r,--len; }
    inline int front() { return w[h].val; }
    inline int back() { return w[t].val; }
    inline void push(int x) {
        while (!empty()&&id[w[t].val]>id[x]) pop_back();
        push_back(x);
    }
} A[N<<1],B[N<<2],*Q1=A+N,*Q=B+N;

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) {
        id[i]=read(),t[i]=read();
        if (!t[i]) t[i]=-1;
    }
    for (re int i=n;i>=1;--i) sum[i]=sum[i+1]+t[i];
    for (re int i=n;i>=1;--i) cnt[i]=cnt[i+1]+(sum[i]==0);
    cnt[n+1]=-1;
    int ans=sum[1]?(abs(sum[1])+k-1)/k:(cnt[1]<k);
    if (!ans) {
        for (re int i=1,j=2;i<k;++i) {
            for (;cnt[j+1]>=k-i;++j) if (!sum[j+1]) Q[0].push(j);
            printf("%d ",id[Q[0].front()]); Q[0].pop_front();
        }
        printf("%d\n",id[n]);
    } else {
        int l=0; id[n+1]=n+1;
        for (re int i=2;i<=n;++i) Q[sum[i]].push_back(i-1);
        for (re int i=1;i<k;++i) {
            int s=n+1;
            for (re int j=sum[l+1]-ans;j<=sum[l+1]+ans;++j) {
                if ((abs(j)+k-i-1)/(k-i)>ans) continue;
                while (!Q[j].empty()&&n-Q[j].front()>=k-i) {
                    if (Q[j].front()>l) Q1[j].push(Q[j].front());
                    Q[j].pop_front();
                }
                while (!Q1[j].empty()&&Q1[j].front()<=l) Q1[j].pop_front();
                if (!Q1[j].empty())
                    if (id[s]>id[Q1[j].front()]) s=Q1[j].front();
            }
            l=s; printf("%d ",id[s]);
        }
        printf("%d\n",id[n]);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 96ms, 内存消耗: 21216K, 提交时间: 2019-02-25 17:47:37

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=500010;
struct data{int l,r,val;}w[N<<2];
int tot;
int n,m,a[N],b[N],sum[N],num[N];
struct Deque
{
	int st,ed,len;
	int empty(){return !len;}
	void push_back(int x){if(len)w[++tot]=(data){ed,0,x},w[ed].r=tot,ed=tot;else w[++tot]=(data){0,0,x},st=ed=tot;len++;}
	void pop_back(){ed=w[ed].l,len--;}
	void pop_front(){st=w[st].r,len--;}
	void push(int x){while(!empty() && a[w[ed].val]>a[x])pop_back();push_back(x);}
	int front(){return w[st].val;}
}A[N<<1],B[N<<2],*q1=N+A,*q=N+B;
int main()
{
#ifndef ONLINE_JUDGE
	file("travel");
#endif
	n=gi();m=gi();
	for(int i=1;i<=n;i++)
	{
		a[i]=gi(),b[i]=gi();
		if(!b[i])b[i]--;
	}
	for(int i=n;i;i--)
		sum[i]=sum[i+1]+b[i];
	for(int i=n;i;i--)
		num[i]=num[i+1]+(sum[i]==0);
	num[n+1]=-1;
	int ans=sum[1]?(abs(sum[1])+m-1)/m:(num[1]<m);
	if(!ans)
	{
//		puts("!");
		for(int i=1,j=2;i<m;i++)
		{
			for(;num[j+1]>=m-i;j++)
				if(!sum[j+1])q[0].push(j);
			printf("%d ",a[q[0].front()]);q[0].pop_front();
		}
	}
	else
	{
//		puts("!!");
		int l=0;a[n+1]=n+1;
		for(int i=2;i<=n;i++)q[sum[i]].push_back(i-1);
		for(int i=1;i<m;i++)
		{
			int s=n+1;
			for(int j=sum[l+1]-ans;j<=sum[l+1]+ans;j++)
			{
				if((abs(j)+m-i-1)/(m-i)>ans)continue;
				while(!q[j].empty() && n-q[j].front()>=m-i)
				{
					if(q[j].front()>l)q1[j].push(q[j].front());
					q[j].pop_front();
				}
				while(!q1[j].empty() && q1[j].front()<=l)q1[j].pop_front();
				if(!q1[j].empty())
					if(a[s]>a[q1[j].front()])s=q1[j].front();
			}
			l=s;printf("%d ",a[s]);
		}
	}
	printf("%d\n",a[n]);
	return 0;
}