이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define ins insert
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define fi first
#define se second
const ll mod = 1e9 + 7;
int n;
vector<ll> a, b;
set<ll> s;
multiset<ll> ms;
ll mult(ll a, ll b)
{
return (a * b) % mod;
}
struct SegTree
{
int sz;
vector<ll> st;
void build(int l, int r, int x)
{
if (l + 1 == r)
{
if (l < n) st[x] = mult(st[x], a[l]);
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x + 1);
build(mid, r, 2*x + 2);
st[x] = mult(st[2*x + 1], st[2*x + 2]);
}
void build(int n)
{
sz = 1;
while (sz < n) sz <<= 1;
st.assign(sz << 1, 1);
build(0, sz, 0);
}
void make(int ind, ll val, int l, int r, int x)
{
if (l + 1 == r)
{
st[x] = val;
return;
}
int mid = (l + r) >> 1;
if (ind < mid) make(ind, val, l, mid, 2*x + 1);
else make(ind, val, mid, r, 2*x + 2);
st[x] = mult(st[2*x + 1], st[2*x + 2]);
}
void make(int ind, ll val)
{
make(ind, val, 0, sz, 0);
}
ll get(int lx, int rx, int l, int r, int x)
{
if (l >= rx || r <= lx) return 1;
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return mult(get(lx, rx, l, mid, 2*x + 1), get(lx, rx, mid, r, 2*x + 2));
}
ll get(int l, int r)
{
return get(l, r + 1, 0, sz, 0);
}
};
struct SegTreeMX
{
int sz;
vector<ll> st;
void build(int l, int r, int x)
{
if (l + 1 == r)
{
if (l < n) st[x] = b[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x + 1);
build(mid, r, 2*x + 2);
st[x] = max(st[2*x + 1], st[2*x + 2]);
}
void build(int n)
{
sz = 1;
while (sz < n) sz <<= 1;
st.assign(sz << 1, 1);
build(0, sz, 0);
}
void make(int ind, ll val, int l, int r, int x)
{
if (l + 1 == r)
{
st[x] = val;
return;
}
int mid = (l + r) >> 1;
if (ind < mid) make(ind, val, l, mid, 2*x + 1);
else make(ind, val, mid, r, 2*x + 2);
st[x] = max(st[2*x + 1], st[2*x + 2]);
}
void make(int ind, ll val)
{
make(ind, val, 0, sz, 0);
}
ll get(int lx, int rx, int l, int r, int x)
{
if (l >= rx || r <= lx) return 1;
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return max(get(lx, rx, l, mid, 2*x + 1), get(lx, rx, mid, r, 2*x + 2));
}
ll get(int l, int r)
{
return get(l, r + 1, 0, sz, 0);
}
};
SegTree st;
SegTreeMX stmx;
ll getans()
{
ll ans = *ms.rbegin();
if (s.empty()) return ans;
vector<int> v;
int k = 1;
for (auto it = s.rbegin(); k <= 30 && it != s.rend(); it++, k++) v.pb(*it);
reverse(all(v));
ll mxb = stmx.get(v[0], (1 == v.size() ? n - 1 : v[1] - 1));
ll x = 1;
ll INF = 1e18;
int f = 0;
int ind = 0;
for (int i = 1; i < v.size(); i++)
{
if (a[v[i]] >= INF/x) f = 1;
if (!f) x *= a[v[i]];
ll bb = stmx.get(v[i], (i + 1 == v.size() ? n - 1 : v[i + 1] - 1));
if (!f && x >= INF/bb) f = 1;
if (!f) x *= bb;
if (f || x > mxb)
{
ind = i;
mxb = bb;
f = 0;
x = 1;
}
else x /= bb;
}
int szs = s.size();
int szv = v.size();
if (szs - (szv - ind) >= 30) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
f = 0;
x = 1;
for (auto it = s.begin(); it != s.end() && *it <= v[ind]; it++)
{
if (a[*it] >= INF/x) f = 1;
if (!f) x *= a[*it];
}
ll bb = stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1));
if (bb >= INF/x) f = 1;
if (!f) x *= bb;
if (f || x > ans) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
else return ans;
}
int init(int N, int X[], int Y[])
{
n = N;
for (int i = 0; i < N; i++)
{
a.pb(X[i]), b.pb(Y[i]);
if (X[i] > 1) s.ins(i);
ms.ins(Y[i]);
}
st.build(n);
stmx.build(n);
return getans();
}
int updateX(int pos, int val)
{
if (a[pos] > 1) s.erase(pos);
a[pos] = val;
if (a[pos] > 1) s.ins(pos);
st.make(pos, val);
return getans();
}
int updateY(int pos, int val)
{
ms.erase(ms.lower_bound(b[pos]));
ms.ins(val);
b[pos] = val;
stmx.make(pos, val);
return getans();
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'll mult(ll, ll)':
horses.cpp:25:18: warning: declaration of 'b' shadows a global declaration [-Wshadow]
25 | ll mult(ll a, ll b)
| ~~~^
horses.cpp:21:15: note: shadowed declaration is here
21 | vector<ll> a, b;
| ^
horses.cpp:25:12: warning: declaration of 'a' shadows a global declaration [-Wshadow]
25 | ll mult(ll a, ll b)
| ~~~^
horses.cpp:21:12: note: shadowed declaration is here
21 | vector<ll> a, b;
| ^
horses.cpp: In member function 'void SegTree::build(int)':
horses.cpp:46:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
46 | void build(int n)
| ~~~~^
horses.cpp:20:5: note: shadowed declaration is here
20 | int n;
| ^
horses.cpp: In member function 'void SegTreeMX::build(int)':
horses.cpp:97:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
97 | void build(int n)
| ~~~~^
horses.cpp:20:5: note: shadowed declaration is here
20 | int n;
| ^
horses.cpp: In function 'll getans()':
horses.cpp:142:72: warning: conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
142 | for (auto it = s.rbegin(); k <= 30 && it != s.rend(); it++, k++) v.pb(*it);
| ^~~
horses.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for (int i = 1; i < v.size(); i++)
| ~~^~~~~~~~~~
horses.cpp:153:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | ll bb = stmx.get(v[i], (i + 1 == v.size() ? n - 1 : v[i + 1] - 1));
| ~~~~~~^~~~~~~~~~~
horses.cpp:165:18: warning: conversion from 'std::set<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
165 | int szs = s.size();
| ~~~~~~^~
horses.cpp:166:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
166 | int szv = v.size();
| ~~~~~~^~
horses.cpp:167:88: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | if (szs - (szv - ind) >= 30) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
| ~~~~~~~~^~~~~~~~~~~
horses.cpp:175:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | ll bb = stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1));
| ~~~~~~~~^~~~~~~~~~~
horses.cpp:178:77: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | if (f || x > ans) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
| ~~~~~~~~^~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:193:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
193 | return getans();
| ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:202:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
202 | return getans();
| ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:211:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
211 | return getans();
| ~~~~~~^~
# | 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... |