| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 86797 | JustasZ | 말 (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) "["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn=5e5+100;
const int mod=1e9+7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll pwr(ll a, ll pw)
{
ll ret=1;
while(pw>0)
{
if(pw&1)ret=(ret*a)%mod;
a=(a*a)%mod;
pw>>=1;
}
return ret;
}
ll modinv(ll a)
{
return pwr(a, mod-2);
}
int N;
ll X[maxn], Y[maxn], seg[maxn*4];
set<int>pos;
void build(int id=1, int l=0, int r=N-1)
{
if(l == r)
{
seg[id]=Y[l];
return;
}
int mid=(l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
seg[id]=max(seg[id*2], seg[id*2+1]);
}
void modify(int pos, ll d, int id=1, int l=0, int r=N-1)
{
if(l == r)
{
seg[id]+=d;
return;
}
int mid=(l+r)/2;
if(pos <= mid)modify(pos, d, id*2, l, mid);
else modify(pos, d, id*2+1, mid+1, r);
seg[id]=max(seg[id*2], seg[id*2+1]);
}
ll query(int x, int y, int id=1, int l=0, int r=N-1)
{
if(l > y || r < x)return 0;
if(l >= x && r <= y)return seg[id];
int mid=(l+r)/2;
return max(query(x, y, id*2, l, mid), query(x, y, id*2+1, mid+1, r));
}
struct BIT
{
ll F[maxn];
void upd(int p, ll val)
{
for(; p<=N; p+=p&-p)
{
F[p]=(F[p]*val)%mod;
}
}
ll get(int p)
{
ll ret=1;
for(; p>0; p-=p&-p)
ret=(ret*F[p])%mod;
return ret;
}
}tree;
ll getans()
{
auto it=prev(pos.end());
ll ret=query(0, N-1);
for(int c=0; c<=30; c++)
{
ret=max(ret, (tree.get(*it+1)*query(*it, N-1))%mod);
if(it == pos.begin())break;
--it;
}
return ret;
}
ll init(int n, int x[], int y[])
{
N=n;
for(int i=0; i<N; i++)
X[i]=x[i], Y[i]=y[i];
for(int i=N-1; i>=0; i--)
if(X[i] >= 2)
pos.insert(i);
build();
for(int i=1; i<=N; i++)
tree.F[i]=1;
for(int i=0; i<N; i++)
tree.upd(i+1, X[i]);
return getans();
}
ll updateX(int p, ll val)
{
tree.upd(p+1, modinv(X[p]));
if(X[p] >= 2)pos.erase(p);
X[p]=val;
if(X[p] >= 2)pos.insert(p);
tree.upd(p+1, val);
return getans();
}
ll updateY(int p, ll val)
{
ll d=val-Y[p];
modify(p, d);
Y[p]=val;
return getans();
}
/*int main()
{
ios_base::sync_with_stdio(false), cin.tie(0);
int A[]={2, 1, 3};
int B[]={3, 4, 1};
cout<<init(3, A, B)<<"\n";
cout<<updateY(1, 2)<<"\n";
return 0;
}*/