| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 352624 | blue | 말 (IOI15_horses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <iostream>
#include <string>
#include <set>
#include <vector>
using namespace std;
long long mod = 1e9 + 7;
long long ll(int a)
{
return (long long)(a);
}
struct segtree
{
int l;
int r;
long long p_mod = 1;
long long p_actual = 1;
long long mx = 1;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
long long rangeprod_mod(int L, int R)
{
if(L > R) return 1;
if(r < L || R < l) return 1;
if(L <= l && r <= R) return p_mod;
return (left->rangeprod_mod(L, R) * right->rangeprod_mod(L, R)) % mod;
}
long long rangeprod_actual(int L, int R)
{
if(L > R) return 1;
if(r < L || R < l) return 1;
if(L <= l && r <= R) return p_actual;
return left->rangeprod_actual(L, R) * right->rangeprod_actual(L, R);
}
long long rangemax(int L, int R)
{
if(r < L || R < l) return 0;
if(L <= l && r <= R) return mx;
return max(left->rangemax(L, R), right->rangemax(L, R));
}
void update(int I, long long V)
{
if(I < l || r < I) return;
if(l == r)
{
p_mod = p_actual = mx = V;
}
else
{
left->update(I, V);
right->update(I, V);
p_mod = (left->p_mod * right->p_mod) % mod;
p_actual = left->p_actual * right->p_actual;
mx = max(left->mx, right->mx);
}
}
};
struct growth
{
int i;
long long x;
};
bool operator < (growth A, growth B)
{
return A.i > B.i;
}
int N;
segtree X;
segtree Y;
set<growth> Xset;
int compute()
{
// if(Xset.size() == 0) return Y.rangemax(0, N-1);
long long maxprod = 1, maxprod_pos = 0;
for(growth g: Xset)
{
maxprod *= g.x;
if(maxprod > ll(1e9))
{
maxprod_pos = g.i + 1;
break;
}
} //maxprod_pos is the last position with a suffix product <= 1e9
long long res = 0, res_pos = -1;
// for(int i = 0; i < N; i++) cout << X.rangeprod_mod(i, i) << ' ';
// cout << '\n';
// for(int i = 0; i < N; i++) cout << X.rangeprod_actual(i, i) << ' ';
// cout << '\n';
// for(int i = 0; i < N; i++) cout << Y.rangemax(i, i) << ' ';
// cout << '\n';
long long compY = 0
for(growth g: Xset)
{
if(g.i < maxprod_pos - 1) break;
long long compX = X.rangeprod_actual(maxprod_pos, g.i);
compY = max(compY, g.X);
if(compX * compY >= res)
{
res = compX * compY;
res_pos = g.i;
}
// if(g.i > 0 && X.rangeprod_actual(maxprod_pos, g.i-1) * Y.rangemax(g.i-1, N-1) > res)
// {
// res = X.rangeprod_actual(maxprod_pos, g.i-1) * Y.rangemax(g.i-1, N-1);
// res_pos = g.i-1;
// }
}
return int( (X.rangeprod_mod(0, res_pos) * Y.rangemax(res_pos, N-1)) % mod );
}
int init(int n, int x[], int y[])
{
N = n;
X = segtree(0, N-1);
Y = segtree(0, N-1);
Xset.insert(growth{-1, 1});
for(int i = 0; i < N; i++)
{
X.update(i, x[i]);
if(x[i] != 1) Xset.insert(growth{i, ll(x[i])});
Y.update(i, ll(y[i]));
}
return compute();
}
int updateX(int pos, int val)
{
int curr_val = X.rangemax(pos, pos);
if(curr_val != 1) Xset.erase(growth{pos, curr_val});
X.update(pos, val);
if(val != 1) Xset.insert(growth{pos, val});
return compute();
}
int updateY(int pos, int val)
{
Y.update(pos, val);
return compute();
}