| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 235194 | anubhavdhar | 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<bits/stdc++.h>
#include "horses.h"
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()
using namespace std;
/*
const short int __PRECISION = 10;
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 5e5+5;
const ll ROOTN = 320;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
*/
#define MAXN 500005
#define MOD 1000000007
ll fxp(ll a, ll n)
{
if(n == 0)
return 1;
if(n&1)
return (a*fxp(a, n-1))%MOD;
ll val = fxp(a, n<<1);
return (val * val)%MOD;
}
#define inv(a) fxp(a, MOD - 2);
ll x[MAXN], y[MAXN], prod, N, invX[MAXN];
set<ii> S;
struct Segtree_aux
{
ll st[4*MAXN], st_max[4*MAXN], sum[4*MAXN];
void upd(int node, int ss, int se, int i, ll val)
{
if(ss > i or se < i)
return;
if(ss == se)
{
st[node] = val % MOD;
st_max[node] = val * y[i];
sum[node] = val;
return;
}
int mid = (ss + se)/2;
upd(node*2+1, ss, mid, i, val);
upd(node*2+2, mid + 1, se, i, val);
st[node] = (st[node*2+1] * st[node*2+2]) % MOD;
if(sum[node*2+1] > 1000000000 and sum[node*2+2] > 1000000000)
sum[node] = -1;
else
sum[node] = sum[node*2+1] * sum[node*2+2];
st_max[node] = max(st_max[node*2 + 1], sum[node*2+1] * st_max[node*2 + 2]);
}
ll quer(int node, int ss, int se, int l, int r)
{
if(ss > r or se < l)
return 1;
if(ss >= l and se <= r)
return st[node];
int mid = (ss + se)/2;
return (quer(node*2+1, ss, mid, l, r) * quer(node*2+2, mid + 1, se, l, r)) % MOD;
}
ll quer2(int node, int ss, int se, int p)
{
// cout<<"asking for ["<<ss<<','<<se<<"] for "<<p<<", having value "<<st_max[node]<<"\n";
if(se < p)
return 0;
if(ss == se)
return ss;
int mid = (ss + se)/2;
if( (mid < p or st_max[node] == st_max[node*2+2] * sum[node*2+1]) && se < N)
return quer2(node*2 + 2, mid + 1, se, p);
return quer2(node*2 + 1, ss, mid, p);
}
Segtree_aux()
{
F0R(i, 4*MAXN)
st[i] = 1;
}
inline void update(int i, ll val)
{
upd(0, 0, MAXN, i, val);
}
inline ll query(int i)
{
return quer(0, 0, MAXN, 0, i);
}
inline ll query2(int i)
{
return quer2(0, 0, MAXN, i);
}
} aux;
int updateX(int i, ll val)
{
aux.update(i, val);
S.erase(mp(-i, x[i]));
prod = (((prod * invX[i])%MOD)*val)%MOD;
x[i] = val;
invX[i] = inv(val);
if(x[i] != 1)
S.insert(mp(-i, x[i]));
int ind = N-1;
ll tmpProd = 1;
for(ii pp : S)
{
tmpProd *= x[-pp.ff];
ind = -pp.ff;
if(tmpProd > 1000000000)
break;
}
ind = aux.query2(ind);
// cout<<"index found is "<<ind<<endl;
return (y[ind] * aux.query(ind))%MOD;
}
int updateY(int pos, int val)
{
y[pos] = val;
aux.update(pos, x[pos]);
int ind = N-1;
ll tmpProd = 1;
for(ii pp : S)
{
tmpProd *= x[-pp.ff];
if(tmpProd > 1000000000)
break;
ind = -pp.ff;
}
ind = aux.query2(ind);
// cout<<"index found is "<<ind<<endl;
return (y[ind] * aux.query(ind))%MOD;
}
int init(int n, int* X, int* Y)
{
N = n;
// ll amt = 0;
prod = 1;
// F0R(i, N)
// {
// x[i] = X[i];
// y[i] = Y[i];
// S.update(i, MAXN, log2(x[i]));
// S.update(i, i, log2(y[i]));
// aux.update(i, X[i]);
// prod *= X[i];
// amt = max(amt, prod*Y[i]);
// }
S.insert(mp(0, 100000000000));
F0R(i, N)
{
x[i] = X[i];
y[i] = Y[i];
invX[i] = inv(X[i]);
S.insert(mp(-i, x[i]));
prod = (prod * x[i])%MOD;
aux.update(i, x[i]);
}
return updateX(0, x[0]);
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, X[120], Y[120], M, j, i, k;
cin>>N;
FOR(i, N)
cin>>X[i];
FOR(i, N)
cin>>Y[i];
cout<<init(N, X, Y)<<endl;
cin>>M;
FOR(i, M)
{
char c;
cin>>c>>j>>k;
if(c == 'X')
cout<<updateX(j, k)<<endl;
else
cout<<updateY(j, k)<<endl;
}
return 0;
}*/