Submission #245864

#	Time	Username	Problem	Language	Result	Execution time	Memory
245864		Evirir	Horses (IOI15_horses)	C++17	34 / 100	1603 ms	70804 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)
{
	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);
}

struct Node{
	ll p, mx;
};

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

bool DEBUG = 0;
const int MAXN = 500005;

int n;
ll x[MAXN],y[MAXN];
set<int> s;
PointSegmentTree st;

ll query()
{
	ll pro=-1;
	ll best=n-1, besty=1;
	int pre=n;
	for(auto it=s.rbegin();it!=s.rend();it++)
	{
		int i=*it;
		cerr<<"i="<<i<<'\n';
		
		cerr<<"pro="<<pro<<'\n';
		
		ll tmpy=st.query(i,pre-1).mx;
		cerr<<"tmpy="<<tmpy<<'\n';
		if(tmpy > pro){
			best=i;
			pro=tmpy;
			besty=tmpy;
			cerr<<"pro="<<pro<<" best="<<best<<" besty="<<besty<<" pro="<<pro<<'\n';
		}
		pro*=x[i];
		if(pro>2e9) break;
		pre=i;
	}
	
	ll p=st.query(0,best).p;
	cerr<<"p="<<p<<" besty="<<besty<<'\n'<<'\n';
	return mult(p, besty);
}

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

int updateX(int pos, int val)
{	
	if(s.find(pos)!=s.end()) s.erase(pos);
	x[pos] = val;
	if(val>1 || pos==0) s.insert(pos);
	st.update(pos,val,0);
	return query();
}

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

Compilation message (stderr)

horses.cpp: In function 'll query()':
horses.cpp:139:10: warning: conversion to 'double' from 'll {aka long long int}' may alter its value [-Wconversion]
   if(pro>2e9) break;
          ^~~
horses.cpp:143:22: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  ll p=st.query(0,best).p;
                      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:166: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:175: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:182:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return query();
         ~~~~~^~

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