이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
const int mod = 1e9 + 7;
int n, curx = 1, x[1 << 19], y[1 << 19], curinv;
double rcurx = 1;
struct node {
int ans, x = 1;
double rans, rx;
} st[1 << 20];
void Build(int node = 1, int left = 1, int right = n) {
if (left == right) {
st[node].x = (curx = (1LL * curx * x[left - 1]) % mod);
st[node].rx = (rcurx += log(x[left - 1]));
st[node].rans = log(y[left - 1]);
st[node].ans = y[left - 1];
return;
}
int m = (left + right) / 2;
Build(2 * node, left, m), Build(2 * node + 1, m + 1, right);
if (st[2 * node].rans + st[2 * node].rx > st[2 * node + 1].rans + st[2 * node + 1].rx)
st[node].ans = 1LL * st[2 * node].ans * st[2 * node].x % mod, st[node].rans = st[2 * node].rans + st[2 * node].rx;
else
st[node].ans = 1LL * st[2 * node + 1].ans * st[2 * node + 1].x % mod, st[node].rans = st[2 * node + 1].rans + st[2 * node + 1].rx;;
}
void Update(pair<int, int> val, int posleft, int posright = n, int node = 1, int left = 1, int right = n) {
if (posleft <= left && right <= posright) {
if (val.first) {
st[node].x = 1LL * st[node].x * val.first % mod * curinv % mod;
st[node].rx = st[node].rx - log(x[posleft - 1]) + log(val.first);
x[posleft - 1] = val.first;
}
else {
st[node].ans = val.second;
st[node].rans = log(val.second);
}
return;
}
int m = (left + right) / 2;
if (posleft <= m)
Update(val, posleft, posright, 2 * node, left, m);
else
Update(val, posleft, posright, 2 * node + 1, m + 1, right);
if (st[2 * node].rans + st[2 * node].rx > st[2 * node + 1].rans + st[2 * node + 1].rx)
st[node].ans = 1LL * st[2 * node].ans * st[2 * node].x % mod, st[node].rans = st[2 * node].rans + st[2 * node].rx;
else
st[node].ans = 1LL * st[2 * node + 1].ans * st[2 * node + 1].x % mod, st[node].rans = st[2 * node + 1].rans + st[2 * node + 1].rx;
}
int pow(int b, int e) {
int ans = 1;
while (e) {
if (e & 1)
ans = 1LL * ans * b % mod;
b = 1LL * b * b % mod, e >>= 1;
}
return ans;
}
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];
Build();
return 1LL * st[1].ans * st[1].x % mod;
}
int updateX(int pos, int val) {
curinv = pow(x[pos], mod - 2);
Update({val,0}, ++pos);
return 1LL * st[1].ans * st[1].x % mod;
}
int updateY(int pos, int val) {
Update({0, val}, pos + 1, pos + 1);
return 1LL * st[1].ans * st[1].x % mod;
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'void Build(int, int, int)':
horses.cpp:17:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
17 | st[node].x = (curx = (1LL * curx * x[left - 1]) % mod);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:26:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
26 | st[node].ans = 1LL * st[2 * node].ans * st[2 * node].x % mod, st[node].rans = st[2 * node].rans + st[2 * node].rx;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:28:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
28 | st[node].ans = 1LL * st[2 * node + 1].ans * st[2 * node + 1].x % mod, st[node].rans = st[2 * node + 1].rans + st[2 * node + 1].rx;;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void Update(std::pair<int, int>, int, int, int, int, int)':
horses.cpp:34:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
34 | st[node].x = 1LL * st[node].x * val.first % mod * curinv % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:50:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
50 | st[node].ans = 1LL * st[2 * node].ans * st[2 * node].x % mod, st[node].rans = st[2 * node].rans + st[2 * node].rx;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:52:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
52 | st[node].ans = 1LL * st[2 * node + 1].ans * st[2 * node + 1].x % mod, st[node].rans = st[2 * node + 1].rans + st[2 * node + 1].rx;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int pow(int, int)':
horses.cpp:59:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
59 | ans = 1LL * ans * b % mod;
| ~~~~~~~~~~~~~~^~~~~
horses.cpp:60:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
60 | b = 1LL * b * b % mod, e >>= 1;
| ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:70:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
70 | return 1LL * st[1].ans * st[1].x % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:76:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
76 | return 1LL * st[1].ans * st[1].x % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:81:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
81 | return 1LL * st[1].ans * st[1].x % 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... |