제출 #1190641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190641		boclobanchat	말 (IOI15_horses)	C++20	17 / 100	327 ms	16440 KiB

horses

#include"horses.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
const long long mod=1e9+7;
const long long INF=1e9;
int fen[MAXN],he[MAXN],seg[MAXN*4],n;
long long pref[MAXN];
long long poww(long long n,long long m)
{
	long long res=n,ans=1;
	while(m)
	{
		if(m&1) ans=ans*res%mod;
		res=res*res%mod,m/=2;
	}
	return ans;
}
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
int walk(int n,int val)
{
	if(val==0) return 0;
	int ans=0;
	for(int i=getlog(n);i+1;i--) if(ans+(1<<i)<=n&&val>fen[ans+(1<<i)]) val-=fen[ans+=(1<<i)];
	return ans+1;
}
void updhe(int i,int n,long long val) { for(;i<=n;i+=i&-i) pref[i]=pref[i]*val%mod; }
long long gethe(int i) { long long ans=1;for(;i;i-=i&-i) ans=ans*pref[i]%mod;return ans; }
void update(int l,int r,int i,int val,int pos)
{
	if(i<l||r<i) return ;
	if(l==r)
	{
		seg[pos]=val;
		return ;
	}
	int mid=(l+r)/2;
	update(l,mid,i,val,pos*2);
	update(mid+1,r,i,val,pos*2+1);
	seg[pos]=max(seg[pos*2],seg[pos*2+1]);
}
int get(int l,int r,int u,int v,int pos)
{
	if(u<=l&&r<=v) return seg[pos];
	int mid=(l+r)/2;
	if(v<=mid) return get(l,mid,u,v,pos*2);
	if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1);
	return max(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1));
}
int solve()
{
	int k=get(n);
	long long res=1,val=1,w=1,ans=0;
	vector<int> vi;
	vi.push_back(n+1);
	for(int i=k;i+1;i--)
	{
		int pos=walk(n,i);
		vi.push_back(max(1,pos));
		if((res*=he[pos])>INF)
		{
			val=gethe(pos);
			break;
		}
	}
	reverse(vi.begin(),vi.end());
	vi.erase(unique(vi.begin(),vi.end()),vi.end());
	int sz=vi.size();
	for(int i=0;i<sz-1;i++)
	{
		int l=vi[i],r=vi[i+1],mx=get(1,n,l,r-1,1);
		w*=he[l],ans=max(ans,w*mx);
	}
	return ans%mod*val%mod;
}
void updatex(int pos,int val)
{
	updhe(pos,n,poww(he[pos],mod-2)*val%mod);
	update(pos,n,-(he[pos]>1)+(val>1));
	he[pos]=val;
}
void updatey(int pos,int val)
{
	update(1,n,pos,val,1);
}
int init(int N,int X[],int Y[])
{
	n=N;
	for(int i=0;i<=N;i++) he[i]=1;
	for(int i=1;i<=N;i++)
	{
		updatex(i,X[i-1]);
		updatey(i,Y[i-1]);
	}
	return solve();
}
int updateX(int pos,int val)
{	
	updatex(pos+1,val);
	return solve();
}
int updateY(int pos,int val)
{
	updatey(pos+1,val);
	return solve();
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23