| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 298814 | davooddkareshki | Horses (IOI15_horses) | C++17 | 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;
#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair
const int maxn = 1e6+10;
const int mod = 1e9+7;
const ll inf = 1e9+10;
int n;
/// baraye Y --> tagir yek adad va maximom yek baze
struct segment_Y
{
int mx[maxn<<2];
segment_Y() {memset(mx, 0, sizeof mx);}
void change(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
mx[v] = val;
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) change(pos, val, v<<1, tl, tm);
else change(pos, val, v<<1|1, tm+1, tr);
mx[v] = max(mx[v<<1],mx[v<<1|1]);
}
int qu(int l, int r, int v = 1, int tl = 1, int tr = n)
{
if(l > r) return 1;
if(tl == l && tr == r) return mx[v];
int tm = (tl + tr) >> 1;
return max(qu(l, min(tm,r), v<<1, tl, tm),
qu(max(tm+1,l), r, v<<1|1, tm+1, tr));
}
} seg_Y;
struct segment_X
{
int mul[maxn<<2];
segment_X() {fill(mul, mul+4*maxn, 1);}
void change(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
mul[v] = val;
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) change(pos, val, v<<1, tl, tm);
else change(pos, val, v<<1|1, tm+1, tr);
mul[v] = (mul[v<<1] * 1ll * mul[v<<1|1]) % mod;
}
int qu(int l, int r, int v = 1, int tl = 1, int tr = n)
{
if(l > r) return 1;
if(tl == l && tr == r) return mul[v];
int tm = (tl + tr) >> 1;
return (qu(l, min(tm,r), v<<1, tl, tm) * 1ll *
qu(max(tm+1,l), r, v<<1|1, tm+1, tr)) % mod;
}
} seg_X;
vector<int> seg[maxn];
void updX(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
seg[v].clear();
if(val >= 2) seg[v].push_back(tl);
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) updX(pos, val, v<<1, tl, tm);
else updX(pos, val, v<<1|1, tm+1, tr);
/// seg[v] nozolie
seg[v].clear();
for(auto x : seg[v<<1|1]) seg[v].push_back(x);
for(auto x : seg[v<<1]) seg[v].push_back(x);
while((int)seg[v].size() > 32ll) seg[v].pop_back();
}
int x[maxn], y[maxn];
int mul(int a, int b) {return min(a*b,inf);}
int mult[33][33];
vector<int> X,Y;
bool cmp(int i, int j)
{
bool sw = 0;
if(i > j) {sw = 1; swap(i,j);}
return (sw ^ (Y[i] < mul(mult[i+1][j],Y[j])));
}
int answer()
{
vector<int> ve = seg[1];
bool DO = 0;
if(ve.empty()) DO = 1;
else if(ve.back() > 1) DO = 1;
if(DO) ve.push_back(1);
reverse(ve.begin(), ve.end());
X.clear(); Y.clear();
vector<int> YES;
for(int i = 0; i < (int)ve.size(); i++)
{
X.push_back(x[ve[i]]);
Y.push_back(seg_Y.qu(ve[i],n));
YES.push_back(i);
//cout<< ve[i] <<" "<< X.back() <<" "<< Y.back() <<"\n";
}
//cout<<"\n";
for(int i = 0; i < 33; i++) for(int j = 0; j < 33; j++) mult[i][j] = 1;
for(int l = 0; l < (int)X.size(); l++)
{
mult[l][l] = X[l];
for(int r = l+1; r < (int)X.size(); r++)
mult[l][r] = mul(mult[l][r-1],X[r]);
}
sort(YES.begin(), YES.end(), cmp);
int id = ve[YES.back()];
//cout<< id <<"\n";
//cout<< y[id] <<"\n";
return (seg_X.qu(1,id) * 1ll * Y[YES.back()]) % mod;
}
int init(int N, int X[], int Y[])
{
n = N;
x[0] = 1; y[0] = 0;
for(int i = 1; i <= n; i++)
{
x[i] = X[i-1];
y[i] = Y[i-1];
updX(i,x[i]);
seg_X.change(i,x[i]);
seg_Y.change(i,y[i]);
}
return answer();
}
int updateX(int pos, int val)
{
pos++;
x[pos] = val;
updX(pos,val);
seg_X.change(pos,val);
return answer();
}
int updateY(int pos, int val)
{
pos++;
y[pos] = val;
seg_Y.change(pos,val);
return answer();
}
/*
int arrX[3] = {2,1,3};
int arrY[3] = {3,4,1};
signed main()
{
//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<< init(3, arrX, arrY) <<"\n";
cout<< updateY(1,2) <<"\n";
}
*/