이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500 * 1000 + 5, mod = 1000 * 1000 * 1000 + 7;
int n;
long long seg1[N * 4];
int seg2[N * 4];
set <int, greater<int> > s;
int a[N], b[N];
void update1(int p, int val, int id = 1, int s = 0, int e = n) {
if (e - s == 1) {
seg1[id] = val;
return;
}
int md = (s + e) / 2;
if (p < md) {
update1(p, val, id * 2, s, md);
}
else {
update1(p, val, id * 2 + 1, md, e);
}
seg1[id] = (seg1[id * 2] * seg1[id * 2 + 1]) % mod;
}
void update2(int p, int val, int id = 1, int s = 0, int e = n) {
if (e - s == 1) {
seg2[id] = val;
return;
}
int md = (s + e) / 2;
if (p < md) {
update2(p, val, id * 2, s, md);
}
else {
update2(p, val, id * 2 + 1, md, e);
}
seg2[id] = max(seg2[id * 2], seg2[id * 2 + 1]);
}
long long get1(int l, int r, int id = 1, int s = 0, int e = n) {
if (r <= s || e <= l) {
return 1;
}
if (l <= s && e <= r) {
return seg1[id];
}
int md = (s + e) / 2;
return (get1(l, r, id * 2, s, md) * get1(l, r, id * 2 + 1, md, e)) % mod;
}
int get2(int l, int r, int id = 1, int s = 0, int e = n) {
if (r <= s || e <= l) {
return 0;
}
if (l <= s && e <= r) {
return seg2[id];
}
int md = (s + e) / 2;
return max(get2(l, r, id * 2, s, md), get2(l, r, id * 2 + 1, md, e));
}
int getans() {
long long mp = 1;
long long ans = 0;
long long u = 1;
int mx = 0, mfor = 0;
long long mmp = 1;
set <int, greater <int> > :: iterator it = s.begin();
while (true) {
int k = *it;
if (k == -1) {
// ans = max(ans, get2(0, n));
break;
}
else {
// cout << "75 " << k << endl;
int t = get2(k, n);
long long s = get1(0, k + 1);
u = s;
s *= t;
s %= mod;
// cout << "78 " << k << " " << t << " " << s << " " << mp << endl;
if (1ll * mp * mx < 1ll * mmp * t) {
mmp = mp;
mx = t;
mfor = k;
}
mp *= a[k];
}
if (mp > mod) {
break;
}
it++;
}
ans = get1(0, mfor + 1) * mx;
ans %= mod;
// cout << "74 " << mfor << " " << mx << " " << ans << endl;
return ans;
}
int init(int nn, int X[], int Y[]) {
n = nn;
fill(seg1, seg1 + n * 4, 1);
for (int i = 0; i < n; i++) {
a[i] = X[i];
b[i] = Y[i];
update1(i, a[i]);
update2(i, b[i]);
if (a[i] > 1) {
s.insert(i);
}
}
s.insert(-1);
s.insert(0);
// cout << "72 " << get1(0, 3) << " " << get2(0, 3) << endl;
return getans();
}
int updateX(int pos, int val) {
update1(pos, val);
if (val > 1) {
s.insert(pos);
}
else if(pos != 0) {
s.erase(pos);
}
a[pos] = val;
return getans();
}
int updateY(int pos, int val) {
update2(pos, val);
a[pos] = val;
return getans();
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'void update1(int, int, int, int, int)':
horses.cpp:13:62: warning: declaration of 's' shadows a global declaration [-Wshadow]
13 | void update1(int p, int val, int id = 1, int s = 0, int e = n) {
| ^
horses.cpp:10:26: note: shadowed declaration is here
10 | set <int, greater<int> > s;
| ^
horses.cpp: In function 'void update2(int, int, int, int, int)':
horses.cpp:28:62: warning: declaration of 's' shadows a global declaration [-Wshadow]
28 | void update2(int p, int val, int id = 1, int s = 0, int e = n) {
| ^
horses.cpp:10:26: note: shadowed declaration is here
10 | set <int, greater<int> > s;
| ^
horses.cpp: In function 'long long int get1(int, int, int, int, int)':
horses.cpp:43:62: warning: declaration of 's' shadows a global declaration [-Wshadow]
43 | long long get1(int l, int r, int id = 1, int s = 0, int e = n) {
| ^
horses.cpp:10:26: note: shadowed declaration is here
10 | set <int, greater<int> > s;
| ^
horses.cpp: In function 'int get2(int, int, int, int, int)':
horses.cpp:54:56: warning: declaration of 's' shadows a global declaration [-Wshadow]
54 | int get2(int l, int r, int id = 1, int s = 0, int e = n) {
| ^
horses.cpp:10:26: note: shadowed declaration is here
10 | set <int, greater<int> > s;
| ^
horses.cpp: In function 'int getans()':
horses.cpp:81:14: warning: declaration of 's' shadows a global declaration [-Wshadow]
81 | long long s = get1(0, k + 1);
| ^
horses.cpp:10:26: note: shadowed declaration is here
10 | set <int, greater<int> > s;
| ^
horses.cpp:101:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
101 | return ans;
| ^~~
horses.cpp:68:12: warning: variable 'u' set but not used [-Wunused-but-set-variable]
68 | long long u = 1;
| ^
# | 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... |