제출 #299017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299017		Hemimor	말 (IOI15_horses)	C++14	17 / 100	1131 ms	49144 KiB

horses

#include "horses.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Segment_Tree{
	private:
	int n;
	vl date;
	public:
	void Init(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vl(2*n-1,1);
	}
	void Update(int k,int x){
		k+=n-1;
		date[k]=x;
		while(k>0){
			k=(k-1)/2;
			date[k]=date[k*2+1]*date[k*2+2]%mod;
		}
	}
	ll Query(int a,int b){
		a+=n-1;b+=n-1;
		ll m=1;
		while(a<b){
			if(a%2==0) (m*=date[a++])%=mod;
			if(b%2==0) (m*=date[--b])%=mod;
			a/=2;b/=2;
		}
		return m;
	}
	ll Open(int k){return date[k+n-1];}
};

template <class T>
class RMQ{
	private:
	int n;
	vector<T> rmq;
	T dfs(int a,int b,int k,int l,int r){
		if(r<=a||b<=l) return 0;
		if(a<=l&&r<=b) return rmq[k];
		int m=(l+r)/2;
		return max(dfs(a,b,k*2+1,l,m),dfs(a,b,k*2+2,m,r));
	}
	public:
	void Init(int n_){
		n=1;
		while(n<n_) n*=2;
		rmq=vector<T>(2*n-1);
	}
	void Update(int k,T x){
		k+=n-1;
		rmq[k]=x;
		while(k>0){
			k=(k-1)/2;
			rmq[k]=max(rmq[k*2+1],rmq[k*2+2]);
		}
	}
	T Query(int a,int b){
		return dfs(a,b,0,0,n);
	}
};

int n;
set<int> st;
RMQ<int> rmq;
Segment_Tree seg;
vi a,b;

int f(){
	ll t=1;
	int id=n;
	vi c;
	while(t<=1000000000){
		auto it=st.lower_bound(id);
		if(it==st.begin()) break;
		it--;
		id=*it;
		c.push_back(id);
		t*=a[id];
	}
	if(c.empty()) return rmq.Query(0,n);
	reverse(c.begin(),c.end());
	int m=(int)c.size();
	t=1;
	ll mx=0;
	for(int i=0;i<m;i++){
		if(i) t*=a[c[i]];
		ll y=rmq.Query(c[i],(i==m-1?n:c[i+1]));
//		cout<<t<<' '<<y<<' '<<c[i]<<' '<<(i==m-1?n:c[i+1])<<endl;
		mx=max(mx,t*y);
	}
//	cout<<mx<<endl;
	return (int)(mx*seg.Query(0,c[0]+1)%mod);
}

int init(int N, int X[], int Y[]) {
	n=N;
	a=b=vi(n);
	rmq.Init(N);
	seg.Init(N);
	for(int i=0;i<n;i++){
		a[i]=X[i],b[i]=Y[i];
		if(a[i]>1) st.insert(i);
		seg.Update(i,a[i]);
		rmq.Update(i,b[i]);
	}
	return f();
}

int updateX(int pos, int val){
	if(a[pos]>1) st.erase(pos);
	a[pos]=val;
	if(a[pos]>1) st.insert(pos);
	seg.Update(pos,val);
	return f();
}

int updateY(int pos, int val) {
	b[pos]=val;
	rmq.Update(pos,val);
	return f();
}

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