Submission #669687

#	Time	Username	Problem	Language	Result	Execution time	Memory
669687		alvingogo	Horses (IOI15_horses)	C++14	0 / 100	1588 ms	49336 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(int x,int y){
	return 1ll*x*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,y;
const int 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;
}
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]);
		y.push_back(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){
		s.erase({-pos,x[pos]});
	}
	x[pos]=val;
	if(x[pos]>=2){
		s.insert({-pos,x[pos]});
	}
	return cal();
}
int updateY(int pos,int val){
	st.update(0,0,n-1,pos,2,val);
	y[pos]=val;
}

Compilation message (stderr)

horses.cpp: In function 'int mul(int, int)':
horses.cpp:11:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |  return 1ll*x*y%mod;
      |         ~~~~~~~^~~~
horses.cpp: In function 'int cal()':
horses.cpp:88:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |    return mul(nw,st.q1(0,0,n-1,0,-h.fs-1));
      |               ^~
horses.cpp:92:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |  return nw;
      |         ^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:122:1: warning: no return statement in function returning non-void [-Wreturn-type]
  122 | }
      | ^

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