Submission #245751

#	Time	Username	Problem	Language	Result	Execution time	Memory
245751		Evirir	Horses (IOI15_horses)	C++17	37 / 100	257 ms	42312 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 1e9+7;

ll add(ll a,ll b)
{
	a+=b;a%=MOD;
	if(a<0) a+=MOD;
	return a;
}
ll mult(ll a, ll b)
{
	//a%=MOD; b%=MOD;
	ll ans=(a*b)%MOD;
	if(ans<0) ans+=MOD;
	return ans;
}
ll pw(ll a, ll b)
{
	ll r=1;
	while(b){
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
ll inverse(ll a)
{
	return pw(a,MOD-2);
}

class PointSegmentTree{
private:
	int size_;
	vector<ll> v;
	
	void update(int p, ll val, int k, int l, int r)
	{
		if(p < l || r < p) return;
		if(l == r){
			v[k]=val;	//modification
			return;
		}
		int mid = (l+r)>>1;
		update(p, val, k*2, l, mid);
		update(p, val, k*2+1, mid+1, r);
		v[k] = merge(v[k*2], v[k*2+1]);
	}
	
	ll query(int s, int e, int k, int l, int r)
	{
		if(e < l || r < s) return 1; //dummy value
		if(s <= l && r <= e) return v[k];
		int mid = (l+r)>>1;
		ll lc = query(s, e, k*2, l, mid);
		ll rc = query(s, e, k*2+1, mid+1, r);
		return merge(lc, rc);
	}
	
public:
	PointSegmentTree(): v(vector<ll>()) {}
	PointSegmentTree(int n){
		for(size_=1;size_<n;) size_<<=1;
		v.resize(size_*4);
	}
	//void reset(){}
	inline ll merge(ll x, ll y){
		return mult(x,y);
	}
	inline void update(int p, ll val){
		update(p, val, 1, 0, size_-1);
	}
	inline ll query(int l, int r){
		return query(l, r, 1, 0, size_-1);
	}
};

bool DEBUG = 0;
const int MAXN = 500005;

int n;
vi x,y;
PointSegmentTree st;

ll query()
{
	ll pro=1;
	ll best=max(0,n-32);
	for(int i=best+1;i<n;i++)
	{
		pro*=x[i];
		if(pro*y[i]>y[best]){
			best=i;
			pro=1;
		}
	}
	//cerr<<"best="<<best<<" st="<<st.query(0,best)<<" y[best]="<<y[best]<<'\n';
	return mult(st.query(0,best), y[best]);
}

int init(int N, int X[], int Y[])
{
	int curmax=Y[0], curx=X[0];
	for(int i=1;i<N;i++){
		if(X[i]==1) curmax=max(curmax, Y[i]);
		else{
			x.pb(curx);
			y.pb(curmax);
			curx=X[i];
			curmax=Y[i];
		}
	}
	x.pb(curx);
	y.pb(curmax);
	
	n=x.size();
	st=PointSegmentTree(n);
	forn(i,0,n){
		//cerr<<"x["<<i<<"]="<<x[i]<<" y["<<i<<"]="<<y[i]<<'\n';
		st.update(i,x[i]);
	}
	
	return query();
}

int updateX(int pos, int val)
{	
	x[pos] = val;
	st.update(pos,val);
	return query();
}

int updateY(int pos, int val)
{
	y[pos] = val;
	return query();
}

Compilation message (stderr)

horses.cpp: In function 'll query()':
horses.cpp:117:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  for(int i=best+1;i<n;i++)
            ~~~~^~
horses.cpp:126:29: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return mult(st.query(0,best), y[best]);
                             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:144:10: warning: conversion to 'int' from 'std::vector<long long int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  n=x.size();
    ~~~~~~^~
horses.cpp:151:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return query();
         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:158:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return query();
         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:164:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return query();
         ~~~~~^~

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