| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 702757 | lukameladze | 말 (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
# include "horses.h"
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
const int N = 5e5 + 5, inf = 2e9, mod = 1e9 + 7;
int n, x[N],y[N],tree_ml[4 * N];
pii tree_mx[4 * N];
int merge_ml(int a, int b) {
return (a * b) % mod;
}
pii merge_mx(pii a, pii b) {
return max(a, b);
}
void build(int node, int le, int ri) {
if (le == ri) {
tree_ml[node] = x[le];
tree_mx[node] = {y[le], le};
return ;
}
int mid = (le + ri) / 2;
build(2 * node, le, mid);
build(2 * node + 1, mid + 1, ri);
tree_ml[node] = merge_ml(tree_ml[2 * node], tree_ml[2 * node + 1]);
tree_mx[node] = merge_mx(tree_mx[2 * node], tree_mx[2 * node + 1]);
}
void update(int node, int le, int ri, int idx, int val, int ty) {
if (le > idx || ri < idx) return ;
if (le == ri) {
if (ty == 0) tree_ml[node] = x[le];
else tree_mx[node] = {y[le], le};
return ;
}
int mid = (le + ri) / 2;
update(2 * node,le, mid,idx,val,ty);
update(2 * node + 1, mid + 1, ri, idx,val,ty);
tree_ml[node] = merge_ml(tree_ml[2 * node], tree_ml[2 * node + 1]);
tree_mx[node] = merge_mx(tree_mx[2 * node], tree_mx[2 * node + 1]);
}
int get_ml(int node, int le, int ri, int start, int end) {
if (le > end || ri < start || start > end) return 1;
if (le >= start && ri <= end) return tree_ml[node];
int mid = (le + ri) / 2;
return merge_ml(get_ml(2 * node, le, mid, start,end), get_ml(2 * node + 1, mid + 1, ri, start, end));
}
pii get_mx(int node, int le, int ri, int start, int end) {
if (le > end || ri < start || start > end) return {-1e9, 0};
if (le >= start && ri <= end) return tree_mx[node];
int mid = (le + ri) / 2;
return merge_mx(get_mx(2 * node, le, mid,start,end), get_mx(2 * node + 1, mid + 1, ri, start, end));
}
set <int> s;
int go() {
auto it = --s.end(); // n + 1
auto it1 = it; it--;
int cur_mx = 1, cnt = 0, optid = n;
while (true) {
cnt++;
int st_y = (*it); int nd_y = (*it1) - 1;
if (st_y == 0) st_y++;
int mx_y = get_mx(1,1,n,st_y, nd_y).f;
if (mx_y > cur_mx) {
optid = get_mx(1,1,n, st_y, nd_y).s;
cur_mx = mx_y;
}
cur_mx *= x[st_y];
if (it1 == s.begin() || cnt > 32 || cur_mx > inf) break;
it--; it1--;
}
return (get_ml(1,1,n,1,optid) * y[optid]) % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
x[0] = 1; y[0] = 1;
for (int i = 1; i <= n; i++) {
x[i] = X[i - 1]; y[i] = Y[i - 1];
if (x[i] != 1) s.insert(i);
}
s.insert(0); s.insert(n + 1);
build(1, 1, n);
return go();
}
int updateX(int pos, int val) {
pos++;
if (x[pos] != 1) {
s.erase(pos);
}
x[pos] = val;
update(1,1,n, pos,val,0);
if (x[pos] != 1) s.insert(pos);
return go();
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
update(1,1,n, pos,val, 1);
return go();
}
/*
main() {
int N;
cin>>N;
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) {
cin>>X[i];
}
for (int i = 0; i < N; i++) {
cin>>Y[i];
}
cout<<init(N,X,Y)<<"\n";
int M;
cin>>M;
for (int i = 0; i < M; i++) {
int type; cin>>type;
int pos; cin>>pos;
int val; cin>>val;
if (type == 1) {
cout<<updateX(pos,val)<<"\n";
} else if (type == 2) {
cout<<updateY(pos,val)<<"\n";
}
}
return 0;
}*/