当前位置 IIS7博客首页 > 【THUWC2020】工资分配 最大化 缩小

    【THUWC2020】工资分配

    作者:ProgrammerStrange 栏目:未分类 时间:2020-06-30 10:03:13

    不要问我为什么我只做thuwc的d1t1 而且是看题解才能做出来
    又是大佬口中的签到题
    由于替换是整个操作,处理出原序列被替换成了某个序列之后的答案,然后对于询问,找到第一次替换发生的位置即可,这个可以枚举每个位置在单调栈上取个min
    刚开始还resize(n+1)....

    #include<bits/stdc++.h>
    using namespace std;
    #define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
    #define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
    #define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
    #define mem(a) memset((a),0,sizeof (a))
    #define O(x) cerr<<#x<<':'<<x<<endl
    #define vec vector<int>
    inline int read(){
    	int x=0,f=1;char ch=getchar();
    	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    	return x*f;
    }
    void wr(int x){
    	if(x<0)x=-x,putchar('-');
    	if(x>=10)wr(x/10);
    	putchar('0'+x%10);
    }
    const int MAXN=1e5+20;
    vec sta[22],a[MAXN],b[MAXN];
    int n,K,pos[MAXN],Q;
    inline void insert(int p,int t){
    	while(!sta[p].empty()&&a[sta[p].back()][p]<=a[t][p])sta[p].pop_back();
    	sta[p].push_back(t);
    }
    inline vec ask(int t){
    	int num=n+1;
    	fp(i,1,K){
    		auto it=lower_bound(sta[i].begin(),sta[i].end(),t,
    							[&](int x,int y){return a[x][i]>a[y][i];});
    		if(it!=sta[i].begin())num=min(num,*--it);
    	}
    	return num==n+1?a[t]:b[num];
    }
    main(){
    	n=read();Q=read();K=read();
    	fp(i,1,n){
    		pos[i]=read();a[i].resize(K+1);
    		fp(j,1,K)a[i][j]=read();
    	}
    	fd(i,n,1){
    		b[i]=ask(i);insert(pos[i],i);
    	}
    	a[0].resize(K+1);
    	while(Q--){
    		fp(j,1,K)a[0][j]=read();b[0]=ask(0);
    		fp(j,1,K)wr(b[0][j]),putchar(' ');putchar('\n');
    	}
    	return 0;
    }