| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 712332 | Nhoksocqt1 | 정렬하기 (IOI15_sorting) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 500005;
const int modl = 1e9+7;
ll fen[MAXN];
int X[MAXN], Y[MAXN], nArr;
#ifdef Nhoksocqt1
int init(int _N, int _X[], int _Y[]);
int updateX(int pos, int val);
int updateY(int pos, int val);
int _X[MAXN], _Y[MAXN];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("HORSES.inp", "r", stdin);
freopen("HORSES.out", "w", stdout);
int _N;
cin >> _N;
for (int i = 0; i < _N; ++i) {
cin >> _X[i];
//_X[i] = Random(1, 1e9); cout << _X[i] << " \n"[i + 1 == _N];
}
for (int i = 0; i < _N; ++i) {
cin >> _Y[i];
//_Y[i] = Random(1, 1e9); cout << _Y[i] << " \n"[i + 1 == _N];
}
cout << init(_N, _X, _Y) << '\n';
int Q;
cin >> Q;
while(Q--) {
int type, pos, val;
cin >> type >> pos >> val;
type = Random(0, 1), pos = Random(0, _N - 1), val = Random(1, 1e9); cout << type << ' ' << pos << ' ' << val << '\n';
if(type == 0) {
cout << updateX(pos, val) << '\n';
} else {
cout << updateY(pos, val) << '\n';
}
}
return 0;
}
#endif // Nhoksocqt1
ll powermod(ll a, int exponent) {
ll res(1);
while(exponent > 0) {
if(exponent & 1)
res = res * a % modl;
a = a * a % modl;
exponent >>= 1;
}
return res;
}
int segx[4 * MAXN], segy[4 * MAXN];
void build(int seg[], int id, int l, int r, int x[]) {
if(l == r) {
seg[id] = x[l];
return;
}
int mid = (l + r) >> 1;
build(seg, id << 1, l, mid, x);
build(seg, id << 1 | 1, mid + 1, r, x);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
void update(int seg[], int pos, int val) {
int id(1), l(1), r(nArr);
while(l != r) {
int mid = (l + r) >> 1;
if(pos <= mid) {
id = id << 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
seg[id] = val;
while(id > 1) {
id >>= 1;
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
}
int findLast(int seg[], int id, int l, int r, int pos, int k) {
if(seg[id] < k || pos < l)
return 0;
if(r <= pos) {
while(l != r) {
int mid = (l + r) >> 1;
if(seg[id << 1 | 1] < k) {
id = id << 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
return l;
}
int mid = (l + r) >> 1;
return max(findLast(seg, id << 1, l, mid, pos, k), findLast(seg, id << 1 | 1, mid + 1, r, pos, k));
}
void modify(int i, int v) {
for (; i <= nArr; i += i & -i)
fen[i] = fen[i] * v % modl;
}
int get(int i) {
ll res(1);
for (; i > 0; i -= i & -i)
res = res * fen[i] % modl;
return res;
}
int query(int seg[], int id, int l, int r, int u, int v) {
if(v < l || u > r)
return 0;
if(u <= l && r <= v)
return seg[id];
int mid = (l + r) >> 1;
return max(query(seg, id << 1, l, mid, u, v), query(seg, id << 1 | 1, mid + 1, r, u, v));
}
typedef pair<ll, ll> pll;
int pos[MAXN];
int calc(void) {
pos[0] = nArr + 1;
ll prod(1);
int nPos(0), opt(nArr);
while(prod <= 1e9) {
prod *= X[opt];
pos[++nPos] = opt;
opt = findLast(segx, 1, 1, nArr, opt - 1, 2);
}
++nPos, prod = 1;
pll ansNow = {0, 0};
ll res = get(opt);
while(nPos--) {
int nxt = pos[nPos];
int maxY = query(segy, 1, 1, nArr, max(1, opt), nxt - 1);
if(!ansNow.se || double(ansNow.fi) / maxY < double(prod) / ansNow.se)
ansNow = {prod, maxY};
prod *= X[nxt];
opt = nxt;
}
ll ans = ansNow.fi % modl * ansNow.se % modl;
return res * ans % modl;
}
int init(int _N, int _X[], int _Y[]) {
nArr = _N;
for (int i = 1; i <= nArr; ++i) {
X[i] = _X[i - 1];
Y[i] = _Y[i - 1];
fen[i] = 1;
}
build(segx, 1, 1, nArr, X);
build(segy, 1, 1, nArr, Y);
for (int i = 1; i <= nArr; ++i)
modify(i, X[i]);
return calc();
}
int updateX(int pos, int val) {
++pos;
modify(pos, powermod(X[pos], modl - 2) * val % modl);
update(segx, pos, val);
X[pos] = val;
return calc();
}
int updateY(int pos, int val) {
++pos;
Y[pos] = val;
update(segy, pos, val);
return calc();
}