| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 795412 | Markynoodle | Horses (IOI15_horses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long
#define fastOI ios_base::sync_with_stdio(false); cin.tie(nullptr);
auto cmp = [](int a, int b){return a > b;};
auto cmp1 = [](pair<ll,ll> a, pair<ll,ll> b){return a.second < b.second;};
ll mod = 1000000007;
vector<ll> segtreex;
vector<ll> segtreey;
void updatex(int l, int r, int pos, int ind, ll x){
int m = l + (r - l)/2;
if(ind < l || ind >= r)return;
if(l == ind && l + 1 == r){
segtreex[pos] = x;
return;
}
updatex(l, m, pos*2, ind, x);
updatex(m, r, pos*2 + 1, ind, x);
segtreex[pos] = (segtreex[pos*2] * segtreex[pos*2 + 1])%mod;
return;
}
ll queryx(int l, int r, int pos, int ql, int qr){
if( ql >= l && qr <= r)return segtreex[pos];
if( qr <= l || ql >= r)return 1;
int m = l + (r-l)/2;
return (queryx(l, m, pos * 2, ql, qr) * queryx(m, r, pos*2 + 1, ql, qr))%mod;
}
void updatey(int l, int r, int pos, int ind, ll x){
int m = l + (r - l)/2;
if(ind < l || ind >= r)return;
if(l == ind && l + 1 == r){
segtreey[pos] = x;
return;
}
updatey(l, m, pos*2, ind, x);
updatey(m, r, pos*2 + 1, ind, x);
segtreey[pos] = max(segtreey[pos*2], segtreey[pos*2 + 1]);
return;
}
ll queryy(int l, int r, int pos, int ql, int qr){
if( ql >= l && qr <= r)return segtreey[pos];
if( qr <= l || ql >= r)return 1;
int m = l + (r-l)/2;
return max(queryy(l, m, pos * 2, ql, qr), queryy(m, r, pos*2 + 1, ql, qr));
}
set<ll> fasts;
int npo2;
vector<ll> x;
vector<ll> y;
int n;
int init(int nn, int xx[], int yy[]){
for(int i = 0; i<n; i++){
x.push_back(xx[i]);
y.push_back(yy[i]);
}
n = nn;
npo2 = __lg(n-1) + 1;
npo2 = (1<<npo2);
segtreex.resize(npo2 * 2, 1);
segtreey.resize(npo2 * 2, 0);
for(int i = 0; i<n; i++){
if(x[i] > 1)updatex(0, npo2, 1, i, x[i]);
if(x[i] > 1)fasts.insert(i);
}
for(int i = 0; i<n; i++){
updatey(0, npo2, 1, i, y[i]);
}
if(fasts.empty()){
return queryy(0, npo2, 1, 0, npo2);
}
vector<pair<ll,ll>> solver(30,{1, 1});
set<ll>::iterator pt = fasts.end();
int opt = (min(30, int(fasts.size())));
int last = n;
ll temppro = 1;
for(int i = 0 ;i < opt; i++){
pt--;
solver[opt - i].first = x[*pt];
solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
last = *pt;
temppro *= x[*pt];
if(temppro >= mod)break;
}
ll startproduct = queryx(0, npo2, 1, 0, last);
temppro = 1;
ll best = 1;
for(int i = 0; i < opt; i++){
temppro *= solver[i].first;
best = max(best, temppro * solver[i].second);
}
best %= mod;
return solve();
}
int solve(){
int sol = 0;
if(fasts.empty()){
return queryy(0, npo2, 1, 0, npo2);
}
vector<pair<ll,ll>> solver(30,{1, 1});
set<ll>::iterator pt = fasts.end();
int opt = (min(30, int(fasts.size())));
int last = n;
ll temppro = 1;
for(int i = 0 ;i < opt; i++){
pt--;
solver[opt - i].first = x[*pt];
solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
last = *pt;
temppro *= x[*pt];
if(temppro >= mod)break;
}
ll startproduct = queryx(0, npo2, 1, 0, last);
temppro = 1;
ll best = 1;
for(int i = 0; i < opt; i++){
temppro *= solver[i].first;
best = max(best, temppro * solver[i].second);
}
best %= mod;
return (best * startproduct)%mod;
//x for growth
// y for prices;
}
int updateX(int pos, int val) {
return 0;
}
int updateY(int pos, int val) {
return 0;
}