| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 199724 | FieryPhoenix | 말 (IOI15_horses) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include <horses.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
ll N;
ll worth[100005],X[500001],Y[500001];
bool over[100005];
set<ll>bigInd;
ll treeMax[1000001],treeMult[1000001];
void updateMax(ll pos, ll val){
pos+=N;
treeMax[pos]=val;
for (pos/=2;pos>=1;pos/=2)
treeMax[pos]=max(treeMax[pos*2],treeMax[pos*2+1]);
}
ll queryMax(ll L, ll R){
L+=N; R+=N;
ll ans=0;
while (L<=R){
if (L%2==1)
ans=max(ans,treeMax[L++]);
if (R%2==0)
ans=max(ans,treeMax[R--]);
L/=2;
R/=2;
}
return ans;
}
void updateMult(ll pos, ll val){
pos+=N;
treeMult[pos]=val;
for (pos/=2;pos>=1;pos/=2)
treeMult[pos]=(treeMult[pos*2]*treeMult[pos*2+1])%MOD;
}
ll queryMult(ll L, ll R){
L+=N; R+=N;
ll ans=1;
while (L<=R){
if (L%2==1)
ans*=treeMult[L++];
ans%=MOD;
if (R%2==0)
ans*=treeMult[R--];
ans%=MOD;
L/=2;
R/=2;
}
return ans;
}
ll calc(){
if (bigInd.size()==0)
return queryMax(0,N-1);
vector<ll>v;
set<ll>::iterator it=bigInd.end();
it--;
for (;;){
v.push_back(*it);
if (it==bigInd.begin() || v.size()==31)
break;
it--;
}
reverse(v.begin(),v.end());
ll M=v.size();
for (ll i=0;i<=M;i++){
worth[i]=0;
over[i]=false;
}
for (ll i=M-1;i>=0;i--){
if (over[i+1])
worth[i]=X[v[i]]*worth[i+1];
else{
ll L=v[i];
ll R;
if (i==M-1)
R=N-1;
else
R=v[i+1]-1;
assert(L<=R);
worth[i]=X[v[i]]*max(queryMax(L,R),worth[i+1]);
}
over[i]=(worth[i]>1000000000) | over[i+1];
if (over[i])
worth[i]%=MOD;
}
return (worth[0]*queryMult(0,v[0]-1))%MOD;
}
ll init(ll n, ll x[], ll y[]){
N=n;
for (ll i=0;i<N;i++){
X[i]=x[i];
Y[i]=y[i];
updateMax(i,Y[i]);
updateMult(i,X[i]);
if (X[i]>1)
bigInd.insert(i);
}
return calc();
}
ll updateX(ll pos, ll val){
if (X[pos]>1 && val==1)
bigInd.erase(pos);
else if (X[pos]==1 && val>1)
bigInd.insert(pos);
X[pos]=val;
updateMult(pos,val);
return calc();
}
ll updateY(ll pos, ll val){
Y[pos]=val;
updateMax(pos,val);
return calc();
}