| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 247670 | fivefourthreeone | 말 (IOI15_horses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 500001;
int n;
set<int> good;
int startpos = -1;
int sgmax[2*mxN];
ll ans = 1;
ll x[mxN], y[mxN];
void build() {
for(int i=n; i<2*n; ++i) sgmax[i] = y[i-n];
for(int i=n-1; i>0; --i) sgmax[i] = max(sgmax[i<<1], sgmax[i<<1|1]);
}
void upd(int p, int val) {
for(sgmax[p+=n] =val; p>0; p>>=1) sgmax[p>>1] = max(sgmax[p], sgmax[p^1]);
}
int qmax(int l, int r) {
r++;
int res = 0;
for(l+=n, r+=n; l<r; l>>=1, r>>=1) {
if(l&1)res = max(res, sgmax[l++]);
if(r&1)res = max(res, sgmax[--r]);
}
return res;
}
ll binpow(ll a, ll b) { ll res = 1; while(b){ if(b&1) res = (res*a)%MOD; b>>=1; a = (a*a)%MOD;}return res;}
ll modInv(ll x) {return binpow(x, MOD-2);}
ll solve() {
if(startpos==-1) return qmax(0, n-1);
ll best= 1;
ll curr = 1;
ll partans = 1;
int start = startpos;
auto it = --good.end();
while(partans<1e9+7) {
partans*=x[*it];
start = *it;
if(it==good.begin())break;
it--;
}
partans = 1;
owo(i, startpos, start){
partans = partans*x[i]%MOD;
}
it = good.lower_bound(start);
while(it!=good.end()) {
curr = curr*(x[*it]);
best = max(best, (ll)qmax(*it, next(it)==good.end() ? n-1 : *next(it))*curr);
it++;
}
return ((ans*partans)%MOD*best%MOD);
}
ll init(int N, ll X[], ll Y[]) {
n = N;
owo(i, 0, mxN) {
x[i] = X[i];
y[i] = Y[i];
}
build();
owo(i, 0, n) {
if(x[i]>1) good.insert(i);
}
auto it = --good.end();
int num = 60;
while(num) {
num--;
if(it==good.begin())break;
it--;
}
startpos = *it;
owo(i, 0, startpos) {
ans = (ans*x[i])%MOD;
}
return solve();
}
ll updateX(int pos, int val) {
if(x[pos]==1&&val!=1) {
good.insert(pos);
if(pos<startpos) {
ans = (ans*val)%MOD;
}else if(pos>startpos){
ans = (ans*x[startpos]%MOD);
auto it = good.upper_bound(startpos);
startpos = (it==good.end() ? -1 : *it);
}
}else if(x[pos]!=1&&val==1) {
auto it = good.find(pos);
if(pos<startpos) {
ans = (ans*modInv(x[pos]))%MOD;
}else if(pos>=startpos) {
if(it!=good.begin()) {
startpos = *prev(it);
}
}
good.erase(good.find(pos));
}
x[pos] = val;
return solve();
}
ll updateY(int pos, int val) {
upd(pos, val);
return solve();
}
int main()
{
//freopen("filename.in", "r", stdin);
//freopen("filename.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
/*int tempn;
ll tempx[mxN];
ll tempy[mxN];
cin>>tempn;
owo(i, 0, tempn) {
cin>>tempx[i];
}
owo(i,0, tempn) {
cin>>tempy[i];
}
cout<<init(tempn, tempx, tempy);*/
return 0;
}