| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 225571 | rqi | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
#define bk back()
#define pb push_back
#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;
const ld PI = acos((ld)-1);
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
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
/**
* Description: modular arithmetic operations
* Source:
* KACTL
* https://codeforces.com/blog/entry/63903
* https://codeforces.com/contest/1261/submission/65632855 (tourist)
* https://codeforces.com/contest/1264/submission/66344993 (ksun)
* Verification:
* https://open.kattis.com/problems/modulararithmetic
*/
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; }
friend void re(mi& a) { ll x; re(x); a = mi(x); }
friend str ts(mi a) { return ts(a.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);
}
/**
* Description: 1D point update, range query where \texttt{comb} is
* any associative operation. If $N$ is not power of 2 then
* operations work but \texttt{seg[1] != query(0,N-1)}.
* Time: O(\log N)
* Source:
* http://codeforces.com/blog/entry/18051
* KACTL
* Verification: SPOJ Fenwick
*/
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);
}
};
/**
* Description: 1D point update, range query where \texttt{comb} is
* any associative operation. If $N$ is not power of 2 then
* operations work but \texttt{seg[1] != query(0,N-1)}.
* Time: O(\log N)
* Source:
* http://codeforces.com/blog/entry/18051
* KACTL
* Verification: SPOJ Fenwick
*/
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
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(MOD)){
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)*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)*q.f));
//ps(*it, curprod, q.f);
it = next(it);
}
return int(curans.s);
}
else{
int ind = *it;
q = mseg.query(0, ind-1);
ckmax(curans, mp(q.f, pseg.query(0, q.s)*q.f));
curprod = 1;
while(it != n1pos.end()){
int r;
if(next(it) == n1pos.end()){
r = N;
}
else{
r = *(next(it));
}
q = mseg.query(*it, r-1);
ckmax(curans, mp(curprod*q.f, pseg.query(0, q.s)*q.f));
curprod*=X[*it];
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();
}