제출 #1254486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254486		Newtonabc	Horses (IOI15_horses)	C++20	17 / 100	81 ms	37704 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1e9+7;
const int K=5e5+10;
const int M=1<<20;
int n;
ll x[K],y[K];
ll mpow(ll base,ll po){
	ll ret=1,mult=base;
	while(po){
		if(po%2) ret=(ret*mult)%MOD;
		po/=2;
		mult=(mult*mult)%MOD;
	}
	return ret;
}
ll mult(ll a,ll b){return (a*b)%MOD;}
ll inv(ll a){return mpow(a,MOD-2);}
struct stree{
	vector<long long> s,lz,arr;
	void init(){
		s.resize(M),lz.resize(M,1),arr.resize(M);
	}
	void deb(){
		for(int i=0;i<n;i++){
			int tmp=query(0,n-1,1,i,i);
			cout<<tmp <<" ";
		}
		cout<<"\n";
	}
	void pushlz(int l,int r,int idx){
		if(lz[idx]==1) return;
		s[idx]=mult(s[idx],lz[idx]);
		if(l!=r) lz[idx*2]=mult(lz[idx*2],lz[idx]),lz[idx*2+1]=mult(lz[idx*2+1],lz[idx]);
		lz[idx]=1;
	}
	void build(int l,int r,int idx){
		if(l==r){
			s[idx]=arr[l];
			return;
		}
		int m=(l+r)/2;
		build(l,m,idx*2);
		build(m+1,r,idx*2+1);
		s[idx]=max(s[idx*2],s[idx*2+1]);
	}
	void update(int l,int r,int idx,int a,int b,int val){
		pushlz(l,r,idx);
		if(a>r || b<l) return;
		if(a<=l && b>=r){
			lz[idx]=mult(lz[idx],val);
			pushlz(l,r,idx);
			return;
		}
		int m=(l+r)/2;
		update(l,m,idx*2,a,b,val);
		update(m+1,r,idx*2+1,a,b,val);
		s[idx]=max(s[idx*2],s[idx*2+1]);
	}
	ll query(int l,int r,int idx,int a,int b){
		pushlz(l,r,idx);
		if(a>r || b<l) return INT_MIN;
		if(a<=l && b>=r) return s[idx];
		int m=(l+r)/2;
		return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
	}
}st;
int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0;i<N;i++) x[i]=X[i],y[i]=Y[i];
	long long ac=1;
	st.init();
	for(int i=0;i<N;i++){
		ac=mult(ac,x[i]);
		st.arr[i]=mult(ac,y[i]);
	}
	st.build(0,N-1,1);
	//st.deb();
	ll tmp=st.query(0,N-1,1,0,N-1);
	return tmp;
}
int updateX(int pos, int val) {	
	st.update(0,n-1,1,pos,n-1,inv(x[pos]));
	//st.deb();
	st.update(0,n-1,1,pos,n-1,val);
	//st.deb();
	x[pos]=val;
	//st.deb();
	ll tmp=st.query(0,n-1,1,0,n-1);
	return tmp;
}

int updateY(int pos, int val) {
	st.update(0,n-1,1,pos,pos,inv(y[pos]));
	//st.deb();
	st.update(0,n-1,1,pos,pos,val);
	//st.deb();
	y[pos]=val;
	//st.deb();
	ll tmp=st.query(0,n-1,1,0,n-1);
	return tmp;
}

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