95分
查看原帖
95分
208967
Hasinon楼主2021/10/11 18:06

WA了一个点,还是270000行出错,求大佬帮忙改题

#include <bits/stdc++.h>
#define G getchar()
#define ll long long
#define mid (l + r) >> 1
#define in cin
#define out cout 
using namespace std;
bool happy1041;
ll time1 = clock();
//
struct node{
	ll ord,x,y,ans;
};
node que[300005],oque[300005];
ll n,m,q;
ll T[600005],lsl[600005];
vector <ll> neww[300005];
ll lowbit(ll a){
	return a&(-a); 
}
ll query(ll num){
	ll to=0,bz=1; bool lb=0;
	while(to+bz<=m+q&&num>T[to+bz]){
		to+=bz;
		if(lb)
		bz<<=1;
		else lb=1;
	} 
	num-=T[to];
	bz>>=1;
	while(bz>=1){
		if(to+bz<=m+q&&num>T[to+bz]){
			to+=bz;
			num-=T[to];
		}
		bz>>=1;
	}
	return to+1;
}
void add(ll po,ll num)
{
	while(po<=m+q){
		T[po]+=num;
		po+=lowbit(po);
	}
}
bool cmp(node a,node b){
	if(a.x<b.x) return true;
	if(a.x==b.x&&a.ord<b.ord) return true;
	return false; 
}
//
bool Happy1041;
void usage() {
	ll time2 = clock();
	cout << "Memory usage: " << (&Happy1041 - &happy1041) / 1024 / 1024 << " Mb , Time usage: " << time2 - time1 << " ms\n";
}
int main() {
//	ifstream in("phalanx.in");
//	ofstream out("phalanx.out");
	in>>n>>m>>q;
	for(int i=1; i<=q; ++i){
		que[i].ord=i;
		in>>que[i].x>>que[i].y;
		oque[i]=que[i];
	}
	sort(que+1,que+q+1,cmp);
	for(int i=1; i<m; ++i) add(i,1);
	add(m+q,1);
	ll numnew=0;
	for(int i=1; i<=q; ++i){
		if(que[i].x!=que[i-1].x){
			numnew=0;
			if(i-1>=1){
				if(que[i-1].ans!=m+q)
				{
					add(que[i-1].ans,1);
					add(++numnew+m-1,-1);	
				}
				ll t1=i-2;
				while(t1>=1&&que[t1].x==que[t1+1].x){
					if(que[t1].ans!=m+q)
					{
						add(que[t1].ans,1);
						add(++numnew+m-1,-1);
					}
					--t1;
				}
			}
			numnew=0;
		}
		que[i].ans=query(que[i].y); 
		oque[que[i].ord].ans=que[i].ans;
		if(que[i].ans!=m+q)
		{
			add(que[i].ans,-1);
			add(++numnew+m-1,1);
		}
	} 
	memset(T,0,sizeof(T));
	for(int i=1; i<=n; ++i){
		lsl[i]=i*m;
		add(i,1);
	} 
	numnew=0;
//	for(int i=1; i<=q; ++i)
//	{
//		out<<oque[i].ans<<endl;
//	}
//	out<<endl;
	for(int i=1; i<=q; ++i){
		ll aba=query(oque[i].x);
		bool lb=1;
		++numnew;
		if(oque[i].ans<=m-1){
			lsl[numnew+n]=(oque[i].x-1)*m+oque[i].ans;
		}
		else if(oque[i].ans<=m+neww[oque[i].x].size()-1){
			lsl[numnew+n]=neww[oque[i].x][oque[i].ans-m];
		}
		else{
			lsl[numnew+n]=lsl[aba];
			lb=0;
		} 
//		for(int j=1; j<=numnew+n; ++j)
//			out<<lsl[j]<<" ";
//		out<<"\n"; 
		out<<lsl[numnew+n]<<endl;
		if(lb)
		neww[oque[i].x].push_back(lsl[aba]);
		add(aba,-1);
		add(numnew+n,1);
	}
	return 0;
}
2021/10/11 18:06
加载中...