이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e9 + 4;
const int MAX = 5e5 + 5;
const int MOD = 1e9 + 7;
int n;
int x[MAX], y[MAX];
int m[MAX * 4], mm[MAX * 4], st[MAX * 4];
void initMul(int idx, int l, int r) {
if (l == r) {
m[idx] = mm[idx] = x[l];
return;
}
int mid = (l + r) / 2;
initMul(idx * 2, l, mid);
initMul(idx * 2 + 1, mid + 1, r);
m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD;
mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]);
}
int get(int idx, int l, int r, int posL, int posR, int type) {
if (posR < l || posL > r) return 1;
if (posL <= l && r <= posR) return type? m[idx]:mm[idx];
int mid = (l + r) / 2;
if (type) {
return (1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type)) % MOD;
}
return min(INF, 1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type));
}
void initSt(int idx, int l, int r) {
if (l == r) {
st[idx] = l;
return;
}
int mid = (l + r) / 2;
initSt(idx * 2, l, mid);
initSt(idx * 2 + 1, mid + 1, r);
int ll = st[idx * 2];
int rr = st[idx * 2 + 1];
if (1LL * y[rr] * get(1, 0, n - 1, ll + 1, rr, 0) >= y[ll]) st[idx] = rr;
else st[idx] = ll;
}
int get() {
int pos = st[1];
return (1LL * get(1, 0, n - 1, 0, pos, 1) * y[pos]) % MOD;
}
void update(int idx, int l, int r, int pos) {
if (pos > r || pos < l) return;
if (l == r) return;
int mid = (l + r) / 2;
update(idx * 2, l, mid, pos);
update(idx * 2 + 1, mid + 1, r, pos);
int ll = st[idx * 2];
int rr = st[idx * 2 + 1];
if (1LL * y[rr] * get(1, 0, n - 1, ll + 1, rr, 0) >= y[ll]) st[idx] = rr;
else st[idx] = ll;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < n; i++) x[i] = X[i], y[i] = Y[i];
initMul(1, 0, n - 1);
// exit(0);
initSt(1, 0, n - 1);
return get();
}
int updateX(int pos, int val) {
x[pos] = val;
update(1, 0, n - 1, pos);
return get();
}
int updateY(int pos, int val) {
y[pos] = val;
update(1, 0, n - 1, pos);
return get();
}
// // #ifdef ONLINE_JUDGE
// int main() {
// int xx[3] = {2, 1, 3};
// int yy[3] = {3, 4, 1};
// cout << init(3, xx, yy) << "\n";
// cout << updateY(1, 2) << "\n";
// }
// #endif
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'void initMul(int, int, int)':
horses.cpp:21:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
21 | m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:22:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
22 | mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get(int, int, int, int, int, int)':
horses.cpp:32:112: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
32 | return (1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type)) % MOD;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:34:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
34 | return min(INF, 1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:55:57: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
55 | return (1LL * get(1, 0, n - 1, 0, pos, 1) * y[pos]) % MOD;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |