| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 235098 | 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
int x[MAXN], y[MAXN];
struct Segtree_aux
{
ll st[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;
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;
}
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;
}
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);
}
} aux;
struct Segtree_main
{
ldd st[4*MAXN], lz[4*MAXN];
inline void push(int node, int ss, int se)
{
if(lz[node] == 0)
return;
// else
// cout<<"lz["<<ss<<','<<se<<"] = "<<lz[node]<<'\n';
st[node] += lz[node];
// cout<<"["<<ss<<","<<se<<"] = "<<st[node]<<" now\n";
if(ss != se)
{
lz[node*2+1] += lz[node];
lz[node*2+2] += lz[node];
}
lz[node] = 0;
}
void upd(int node, int ss, int se, int l, int r, ldd val)
{
push(node, ss, se);
if(ss > r or se < l)
return;
if(ss >= l and se <= r)
{
lz[node] += val;
// cout<<"added "<<val<<" to the entire range ["<<ss<<","<<se<<"] \n";
push(node, ss, se);
return;
}
int mid = (ss + se)/2;
upd(node*2+1, ss, mid, l, r, val);
upd(node*2+2, mid + 1, se, l, r, val);
st[node] = max(st[node*2+1], st[node*2+2]);
// cout<<"updated ["<<ss<<','<< se<<"] to "<<st[node]<<'\n';
}
int quer(int node, int ss, int se)
{
// cout<<"Asking ["<<ss<<' '<<se<<"] -> "<<st[node]<<'\n';
// push(node, ss, se);
if(ss == se)
return ss;
int mid = (ss + se)/2;
push(node*2+1, ss, mid);
if(st[node*2+1] == st[node])
return quer(node*2+1, ss, mid);
push(node*2+2,mid +1, se);
return quer(node*2+2, mid + 1, se);
}
Segtree_main()
{
F0R(i, 4*MAXN)
st[i] = lz[i] = 0;
}
inline void update(int l, int r, ldd val)
{
// cout<<"asked for update("<<l<<','<<r<<','<<val<<")\n";
upd(0, 0, MAXN, l, r, val);
}
inline int query()
{
push(0, 0, MAXN);
int i = quer(0, 0, MAXN);
// cout<<"index found is "<<i<<'\n';
ll p = aux.query(i) * y[i];
return p % MOD;
}
} S;
int updateX(int pos, ll val)
{
aux.update(pos, val);
S.update(pos, MAXN, log2(val) - log2(x[pos]));
x[pos] = val;
return S.query();
}
int updateY(int pos, int val)
{
// aux.update(pos, val);
S.update(pos, pos, log2(val) - log2(y[pos]));
y[pos] = val;
return S.query();
}
int init(int N, int* X, int* Y)
{
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]);
}
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;
}*/