Submission #225576

#	Time	Username	Problem	Language	Result	Execution time	Memory
225576		rqi	Horses (IOI15_horses)	C++14	100 / 100	770 ms	57080 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

struct mi {
	typedef decay<decltype(MOD)>::type T; 
 	/// don't silently convert to T
	T v; explicit operator T() const { return v; }
	mi() { v = 0; }
	mi(ll _v) { 
		v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
		if (v < 0) v += MOD;
	}
	friend bool operator==(const mi& a, const mi& b) { 
		return a.v == b.v; }
	friend bool operator!=(const mi& a, const mi& b) { 
		return !(a == b); }
	friend bool operator<(const mi& a, const mi& b) { 
		return a.v < b.v; }
   
	mi& operator+=(const mi& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	mi& operator-=(const mi& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	mi& operator*=(const mi& m) { 
		v = (ll)v*m.v%MOD; return *this; }
	mi& operator/=(const mi& m) { return (*this) *= inv(m); }
	friend mi pow(mi a, ll p) {
		mi ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend mi inv(const mi& a) { assert(a.v != 0); 
		return pow(a,MOD-2); }
		
	mi operator-() const { return mi(-v); }
	mi& operator++() { return *this += 1; }
	mi& operator--() { return *this -= 1; }
	friend mi operator+(mi a, const mi& b) { return a += b; }
	friend mi operator-(mi a, const mi& b) { return a -= b; }
	friend mi operator*(mi a, const mi& b) { return a *= b; }
	friend mi operator/(mi a, const mi& b) { return a /= b; }
};
typedef vector<mi> vmi;
typedef pair<mi,mi> pmi;
typedef vector<pmi> vpmi;

vector<vmi> comb;
void genComb(int SZ) {
	comb.assign(SZ,vmi(SZ)); comb[0][0] = 1;
	FOR(i,1,SZ) F0R(j,i+1) 
		comb[i][j] = comb[i-1][j]+(j?comb[i-1][j-1]:0);
}

template<class T> struct MaxSeg { // comb(ID,b) = b
	const T ID = mp(0, 0); T comb(T a, T b) { return max(a, b); } 
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// sum on interval [l, r]
		T ra = ID, rb = ID; 
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};

template<class T> struct ProdSeg { // comb(ID,b) = b
	const T ID = mi(1); T comb(T a, T b) { return a*b; } 
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// sum on interval [l, r]
		if(l > r) return 1;
		T ra = ID, rb = ID; 
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};

const int mx = 500005;
int N;
ll X[mx];
ll Y[mx];
MaxSeg<pair<ll, int>> mseg; //value, index of Y[]
ProdSeg<mi> pseg; //X values
set<int> n1pos; //positions of non 1 X values
const ll MAXVAL = ll(MOD);
int query(){
	//ps("QUERY");
	if(sz(n1pos) == 0){
		return int(mseg.query(0, N-1).f);
	}
	ll curprod = 1;
	auto it = n1pos.end();
	while(curprod <= ll(MAXVAL)){
		if(it == n1pos.begin()){
			break;
		}
		it = prev(it);
		int ind = *it;
		curprod*=X[ind];
	}

	pair<ll, mi> curans = mp(0, 0);
	pair<ll, int> q;


	if(it == n1pos.begin()){

		int ind = *it;
		if(ind != 0){
			q = mseg.query(0, ind-1);
			ckmax(curans, mp(q.f, pseg.query(0, q.s)*mi(q.f)));
		}
		curprod = 1;
		while(it != n1pos.end()){
			int r;
			if(next(it) == n1pos.end()){
				r = N; 
			}
			else{
				r = *(next(it));
			}
			curprod*=X[*it];
			q = mseg.query(*it, r-1);
			ckmax(curans, mp(curprod*q.f, pseg.query(0, q.s)*mi(q.f)));
			//ps(*it, curprod, q.f);
			it = next(it);
		}
		return int(curans.s);
	}
	else{
		curprod = 1;
		auto it2 = it;
		while(it != n1pos.end()){
			if(it != it2) curprod*=X[*it];
			int r;
			if(next(it) == n1pos.end()){
				r = N; 
			}
			else{
				r = *(next(it));
			}
			q = mseg.query(*it, r-1);
			//cout << *it << " " << q.f << " " << q.s << " " << curprod*q.f << " " << int(pseg.query(0, q.s)*mi(q.f)) << "\n";
			ckmax(curans, mp(curprod*q.f, pseg.query(0, q.s)*mi(q.f)));
			
			it = next(it);
		}
	return int(curans.s);
	}
	
}

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];
	}
	mseg.init(N+5);
	pseg.init(N+5);
	for(int i = 0; i < N; i++){
		mseg.upd(i, mp(Y[i], i));
		pseg.upd(i, mi(X[i]));
		if(X[i] != 1) n1pos.insert(i);
	}
	return query();
}

int updateX(int pos, int val) {	
	if(X[pos] != 1) n1pos.erase(pos);
	pseg.upd(pos, mi(val));
	X[pos] = val;
	if(X[pos] != 1) n1pos.ins(pos);
	return query();
}

int updateY(int pos, int val) {
	//ps(pos, val);
	mseg.upd(pos, mp(ll(val), pos));
	Y[pos] = val;
	return query();
}

Compilation message (stderr)

horses.cpp: In constructor 'mi::mi(ll)':
horses.cpp:89:31: warning: conversion to 'mi::T {aka int}' from 'll {aka long long int}' may alter its value [-Wconversion]
   v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
       ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
horses.cpp:89:31: warning: conversion to 'mi::T {aka int}' from 'll {aka long long int}' may alter its value [-Wconversion]
horses.cpp: In member function 'mi& mi::operator*=(const mi&)':
horses.cpp:106:16: warning: conversion to 'mi::T {aka int}' from 'll {aka long long int}' may alter its value [-Wconversion]
   v = (ll)v*m.v%MOD; return *this; }
       ~~~~~~~~~^~~~
horses.cpp: In function 'void setIn(std::__cxx11::string)':
horses.cpp:70:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void setOut(std::__cxx11::string)':
horses.cpp:71:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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