| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 221806 | patrikpavic2 | 말 (IOI15_horses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* user: ppavic
* fname: Patrik
* lname: Pavić
* task: horses
* score: 100.0
* date: 2019-06-23 09:59:51.864112
*/
#include "horses.h"
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#define PB push_back
using namespace std;
typedef __int128 ll;
typedef pair < int, int > pii;
typedef vector < int > vi;
const int OFF = (1 << 19);
const ll MOD = 1e9 + 7;
const int N = 1e6 + 500;
ll mul[2 * OFF];
ll mx[2 * OFF], n, X[N], Y[N];
set < int > s;
vi v;
ll query_mul(int i,int a,int b,int lo,int hi){
if(lo <= a && b <= hi) return mul[i];
if(a > hi || b < lo) return 1;
return query_mul(2 * i, a, (a + b) / 2, lo, hi) * query_mul(2 * i + 1, (a + b) / 2 + 1, b, lo, hi) % MOD;
}
ll query_mx(int i,int a,int b,int lo,int hi){
if(lo <= a && b <= hi) return mx[i];
if(a > hi || b < lo) return 1;
return max(query_mx(2 * i, a, (a + b) / 2, lo, hi), query_mx(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}
void update_mul(int i,ll X){
if(mul[OFF + i] > 1) s.erase(i);
if(X > 1) s.insert(i);
mul[OFF + i] = X;
for(i = (i + OFF) / 2; i ; i /= 2)
mul[i] = mul[2 * i] * mul[2 * i + 1] % MOD;
}
void update_mx(int i, ll Y){
mx[OFF + i] = Y;
for(i = (i + OFF) / 2; i ; i /= 2)
mx[i] = max(mx[2 * i], mx[2 * i + 1]);
}
ll solve(){
ll cur = 1, sol = 1;
vi v;
auto it = s.rbegin();
v.PB(n);
//printf("s %d\n", s.size());
for(; v.size() <= s.size() && cur < MOD;){
v.PB(*it); cur *= X[*it]; it++;
if(cur >= (ll)MOD) break;
}
reverse(v.begin(), v.end());
cur = 1;
for(int i = 0;i + 1 < v.size();i++){
cur *= (ll)X[v[i]];
//printf("cur %lld mx %lld\n", cur, query_mx(1, 0, OFF - 1,v[i], v[i + 1] - 1));
sol = max(sol, cur * query_mx(1, 0, OFF - 1,v[i], v[i + 1] - 1));
}
//printf("gotov\n");
if(v.size() > s.size()) return max(sol, (ll)mx[1]) % MOD;
return sol % (ll)MOD * query_mul(1, 0, OFF - 1, 0, v[0] - 1) % MOD;
}
int init(int N, int XX[], int YY[]) {
for(int i = 0;i < N;i++) X[i] = XX[i], Y[i] = YY[i];
n = N;
for(int i = 0;i < n;i++)
update_mul(i, X[i]), update_mx(i, Y[i]);
return solve();
}
int updateX(int pos, int val) {
update_mul(pos, val); X[pos] = val;
return solve();
}
int updateY(int pos, int val) {
update_mx(pos, val); Y[pos] = val;
return solve();
}