結果

問題 No.1405 ジグザグロボット
ユーザー qiuzx
提出日時 2025-04-22 21:20:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 3,153 ms
コード長 5,124 bytes
コンパイル時間 3,487 ms
コンパイル使用メモリ 228,716 KB
実行使用メモリ 60,892 KB
最終ジャッジ日時 2025-04-22 21:20:39
合計ジャッジ時間 9,815 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 300010
#define M ((1<<20)+10)
using namespace std;
struct SegT0{
	int lo[M],hi[M],val[M],pd[M];
	void build(int x,int l,int r){
		lo[x]=l,hi[x]=r,val[x]=pd[x]=0;
		if(l==r) return;
		int mid=(l+r)>>1,a=x<<1;
		build(a,l,mid);
		build(a|1,mid+1,r);
		return;
	}
	void pushdown(int x){
		int a=x<<1;
		val[a]+=pd[x],pd[a]+=pd[x];
		val[a|1]+=pd[x],pd[a|1]+=pd[x];
		pd[x]=0;
		return;
	}
	void update(int x,int l,int r,int v){
		int tl=lo[x],tr=hi[x];
		if(l<=tl&&tr<=r){
			val[x]+=v,pd[x]+=v;
			return;
		}
		if(pd[x]!=0) pushdown(x);
		int mid=(tl+tr)>>1,a=x<<1;
		if(mid>=l) update(a,l,r,v);
		if(mid<r) update(a|1,l,r,v);
		val[x]=min(val[a],val[a|1]);
		return;
	}
	int find(int x){
		if(val[x]>0) return -1;
		int tl=lo[x],tr=hi[x];
		if(tl==tr) return tl;
		if(pd[x]!=0) pushdown(x);
		int mid=(tl+tr)>>1,a=x<<1;
		int ret=find(a);
		return ret==-1?find(a|1):ret;
	}
}segt0;
struct SegT1{
	int lo[M],hi[M];
	ll pd[M];
	pair<ll,int> val[M];
	void build(int x,int l,int r){
		lo[x]=l,hi[x]=r,pd[x]=0;
		if(l==r){
			val[x]=make_pair(-LINF,l);
			return;
		}
		int mid=(l+r)>>1,a=x<<1;
		build(a,l,mid);
		build(a|1,mid+1,r);
		val[x]=max(val[a],val[a|1]);
		return;
	}
	void pushdown(int x){
		int a=x<<1;
		val[a].F+=pd[x],pd[a]+=pd[x];
		val[a|1].F+=pd[x],pd[a|1]+=pd[x];
		pd[x]=0;
		return;
	}
	void update(int x,int l,int r,ll v){
		int tl=lo[x],tr=hi[x];
		if(l<=tl&&tr<=r){
			val[x].F+=v,pd[x]+=v;
			return;
		}
		if(pd[x]!=0) pushdown(x);
		int mid=(tl+tr)>>1,a=x<<1;
		if(mid>=l) update(a,l,r,v);
		if(mid<r) update(a|1,l,r,v);
		val[x]=max(val[a],val[a|1]);
		return;
	}
	void modify(int x,int l,ll v){
		int tl=lo[x],tr=hi[x];
		if(tl==tr){
			val[x]=make_pair(v,l);
			return;
		}
		if(pd[x]!=0) pushdown(x);
		int mid=(tl+tr)>>1,a=x<<1;
		if(mid>=l) modify(a,l,v);
		else modify(a|1,l,v);
		val[x]=max(val[a],val[a|1]);
		return;
	}
	pair<ll,int> query(int x,int l,int r){
		int tl=lo[x],tr=hi[x];
		if(l<=tl&&tr<=r) return val[x];
		if(pd[x]!=0) pushdown(x);
		int mid=(tl+tr)>>1,a=x<<1;
		pair<ll,int> ret=make_pair(-LINF,-INF);
		if(mid>=l) ret=max(ret,query(a,l,r));
		if(mid<r) ret=max(ret,query(a|1,l,r));
		return ret;
	}
}segt1;
int n,m=0,sx,sy,pre[N],g[N],lo[N],hi[N],delta[N];
bool vis[N];
ll f[N];
pair<int,int> seq[N];
vector<pair<int,int> > upds[N];
string s,pth[N];
pair<ll,int> calc(int v){
	segt1.build(1,0,m-1);
	f[0]=0,g[0]=0,pre[0]=-1;
	for(int i=0;i<m;i++){
		segt1.modify(1,i,f[i]);
		for(auto [x,y]:upds[i]) segt1.update(1,0,x,y);
		auto mx=segt1.query(1,0,i);
		pre[i+1]=mx.S,f[i+1]=mx.F-v,g[i+1]=g[mx.S]+1;
	}
	return make_pair(f[m],g[m]);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>sx>>sy>>s;
	s+="S";
	for(int i=0,lst=0;i<s.size();i++) if(s[i]=='S'){
		seq[m++]=make_pair(lst,i-1);
		lst=i+1;
	}
	if(m<=sy){
		cout<<"-1\n";
		return 0;
	}
	segt0.build(1,0,m-1);
	for(int i=0;i<m;i++){
		int v=0;
		for(int j=seq[i].F;j<=seq[i].S;j++){
			if(s[j]=='L'){
				int x=segt0.find(1);
				if(x==-1) x=i+1;
				if(x>0){
					segt0.update(1,0,x-1,-1);
					upds[i].push_back(make_pair(x-1,-1));
				}
			}
			else{
				segt0.update(1,0,i,1);
				v++;
			}
		}
		if(v) upds[i].push_back(make_pair(i,v));
	}
	int l=0,r=n+1;
	while(l<r){
		int mid=(l+r)>>1;
		if(calc(mid).S>=sy+1) l=mid+1;
		else r=mid;
	}
	l--;
	vector<int> p0,p1,pos;
	auto v0=calc(l);
	for(int i=m;i;i=pre[i]) p0.push_back(pre[i]);
	auto v1=calc(l+1);
	for(int i=m;i;i=pre[i]) p1.push_back(pre[i]);
	ll tot;
	if(v0.S==sy+1){
		tot=v0.F+1ll*l*v0.S;
		pos=p0;
	}
	else{
		tot=((v1.F+1ll*(l+1)*v1.S)-(v0.F+1ll*l*v0.S))*(ll)(sy+1-v0.S)/(ll)(v1.S-v0.S);
		tot+=v0.F+1ll*l*v0.S;
		pos=p1;
		for(auto i:p1) vis[i]=true;
		for(auto i:p0) if(pos.size()<=sy&&(!vis[i])) pos.push_back(i);
	}
	if(tot<sx){
		cout<<"-1\n";
		return 0;
	}
	assert((int)pos.size()==sy+1);
	sort(pos.begin(),pos.end());
	tot-=sx;
	for(int i=0,v=0;i<=sy;i++){
		pth[i]="";
		for(int j=pos[i];j<(i==sy?m:pos[i+1]);j++) for(int k=seq[j].F;k<=seq[j].S;k++) pth[i]+=s[k];
		lo[i]=v,hi[i]=v;
		for(auto c:pth[i]){
			v=max(lo[i],v+(c=='L'?-1:1));
			hi[i]=max(hi[i],v);
		}
	}
	for(int i=sy;i>=0&&tot;i--){
		int v0=lo[i];
		for(auto c:pth[i]) v0=max(lo[i],v0+(c=='L'?-1:1));
		int l=lo[i],r=hi[i];
		while(l<r){
			int mid=(l+r)>>1,v=lo[i];
			for(auto c:pth[i]) v=max(lo[i],min(mid,v+(c=='L'?-1:1)));
			if(v0-v<=tot) r=mid;
			else l=mid+1;
		}
		hi[i]=l;
		int v=lo[i];
		for(auto c:pth[i]) v=max(lo[i],min(hi[i],v+(c=='L'?-1:1)));
		tot-=v0-v;
		delta[i]=v0-v;
	}
	vector<pair<int,int> > ans;
	for(int i=0,s=0;i<=sy;i++){
		lo[i]-=s,hi[i]-=s;
		s+=delta[i];
		ans.push_back(make_pair(lo[i]-1,i));
		ans.push_back(make_pair(hi[i]+1,i));
	}
	for(int i=0;i<=sy;i++) for(int j=lo[i];j<=hi[i];j++){
		if(i==sy||j<lo[i+1]||j>hi[i+1]) ans.push_back(make_pair(j,i+1));
	}
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	cout<<ans.size()<<'\n';
	for(auto [x,y]:ans) cout<<x<<" "<<y<<'\n';
	return 0;
}
0