Submission #669702

#	Time	Username	Problem	Language	Result	Execution time	Memory
669702		alvingogo	Horses (IOI15_horses)	C++14	100 / 100	505 ms	48324 KiB

horses

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

const int mod=1e9+7;
int mul(long long x,int y){
	return 1ll*(x%mod)*y%mod;
}
struct ST{
	vector<pair<int,int> > st;
	void init(int n){
		st.resize(4*n);
	}
	void pull(int v){
		st[v].fs=mul(st[2*v+1].fs,st[2*v+2].fs);
		st[v].sc=max(st[2*v+1].sc,st[2*v+2].sc);
	}
	void update(int v,int L,int R,int p,int t,int x){
		if(L==R){
			if(t==1){
				st[v].fs=x;
			}
			else{
				st[v].sc=x;
			}
			return;
		}
		int m=(L+R)/2;
		if(p<=m){
			update(2*v+1,L,m,p,t,x);
		}
		else{
			update(2*v+2,m+1,R,p,t,x);
		}
		pull(v);
	}
	int q1(int v,int L,int R,int l,int r){
		if(r<l){
			return 1;
		}
		if(L==l && r==R){
			return st[v].fs;
		}
		int m=(L+R)/2;
		if(r<=m){
			return q1(2*v+1,L,m,l,r);
		}
		else if(l>m){
			return q1(2*v+2,m+1,R,l,r);
		}
		else{
			return mul(q1(2*v+1,L,m,l,m),q1(2*v+2,m+1,R,m+1,r));
		}
	}
	int q2(int v,int L,int R,int l,int r){
		if(L==l && r==R){
			return st[v].sc;
		}
		int m=(L+R)/2;
		if(r<=m){
			return q2(2*v+1,L,m,l,r);
		}
		else if(l>m){
			return q2(2*v+2,m+1,R,l,r);
		}
		else{
			return max(q2(2*v+1,L,m,l,m),q2(2*v+2,m+1,R,m+1,r));
		}
	}
}st;

set<pair<int,int> > s;
vector<int> x;
const long long inf=2e9;
int n;

int cal(){
	long long nw=1;
	int lst=n;
	for(auto h:s){
		nw=max(nw,(long long)st.q2(0,0,n-1,-h.fs,lst-1));
		nw*=h.sc;
		if(nw>=inf){
			return mul(nw,st.q1(0,0,n-1,0,-h.fs-1));
		}
		lst=-h.fs;
	}
	return nw%mod;
}
int init(int N,int X[],int Y[]){
	st.init(N);
	n=N;
	for(int i=0;i<n;i++){
		st.update(0,0,n-1,i,1,X[i]);
		x.push_back(X[i]);
		st.update(0,0,n-1,i,2,Y[i]);
		if(X[i]>=2 || i==0){
			s.insert({-i,X[i]});
		}
	}
	return cal();
}
int updateX(int pos,int val){
	st.update(0,0,n-1,pos,1,val);
	if(x[pos]>=2 || pos==0){
		assert(s.find(pair<int,int>(-pos,x[pos]))!=s.end());
		s.erase({-pos,x[pos]});
	}
	x[pos]=val;
	if(x[pos]>=2 || pos==0){
		s.insert({-pos,x[pos]});
	}
	return cal();
}
int updateY(int pos,int val){
	st.update(0,0,n-1,pos,2,val);
	return cal();
}

/*
int main() {
	int n;
	cin >> n;
	int u[n]={0},v[n]={0};
	for(int i=0;i<n;i++){
		cin >> u[i];
	}
	for(int i=0;i<n;i++){
		cin >> v[i];
	}
	cout << init(n,u,v) << "\n";
	int q;
	cin >> q;
	while(q--){
		int t;
		cin >> t;
		int x,y;
		cin >> x >> y;
		if(t==1){
			cout << updateX(x,y) << "\n";		
		}
		else{
			cout << updateY(x,y) << "\n";
		}
	}
	return 0;
}
*/

Compilation message (stderr)

horses.cpp: In function 'int mul(long long int, int)':
horses.cpp:11:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |  return 1ll*(x%mod)*y%mod;
      |         ~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int cal()':
horses.cpp:92:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |  return nw%mod;
      |         ~~^~~~

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