이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int) 1e9 + 7;
int add(int a, int b) {
if (a + b >= MOD) return a + b - MOD;
return a + b;
}
int mul(int a, int b) {
return (long long) a * b % MOD;
}
int n;
vector<int> x, y;
set<int> st;
struct node {
int l, r, mx, pr;
node *left, *right;
} *root;
node *build(int l, int r) {
if (l == r) return new node{l, r, y[l], x[l], nullptr, nullptr};
node *left = build(l, (l + r) / 2);
node *right = build((l + r) / 2 + 1, r);
return new node{l, r, max(left->mx, right->mx), mul(left->pr, right->pr), left, right};
}
void update(node *cur, int pos) {
if (cur->l == cur->r) {
cur->mx = y[pos], cur->pr = x[pos];
return;
}
if (pos <= cur->left->r) update(cur->left, pos);
else update(cur->right, pos);
cur->mx = max(cur->left->mx, cur->right->mx);
cur->pr = mul(cur->left->pr, cur->right->pr);
}
int query_mx(node *cur, int l, int r) {
if (cur->l > r || cur->r < l) return 0;
if (l <= cur->l && cur->r <= r) return cur->mx;
return max(query_mx(cur->left, l, r), query_mx(cur->right, l, r));
}
int query_pr(node *cur, int l, int r) {
if (cur->l > r || cur->r < l) return 1;
if (l <= cur->l && cur->r <= r) return cur->pr;
return mul(query_pr(cur->left, l, r), query_pr(cur->right, l, r));
}
int calc_ans() {
int i = 0, prev = n, best = -1, best_next = -1;
st.insert(0);
for (auto it = st.rbegin(); it != st.rend() && i < 30; it++, i++) {
int cost = query_mx(root, *it, prev - 1);
long long cur = query_mx(root, best, best_next - 1);
bool better = true;
for (auto it2 = st.lower_bound(best); *it2 != *it; it2--) {
cur *= x[*it2];
if (cur > cost) {
better = false;
break;
}
}
if (better) best = *it, best_next = prev;
}
return mul(query_pr(root, 0, best), query_mx(root, best, best_next - 1));
}
int init(int N, int X[], int Y[]) {
n = N;
x.assign(X, X + n);
y.assign(Y, Y + n);
for (int i = 0; i < n; i++) if (x[i] != 1) st.insert(i);
root = build(0, n - 1);
return calc_ans();
}
int updateX(int pos, int val) {
if (x[pos] != val) {
if (val != 1) st.insert(pos);
else if (st.count(pos)) st.erase(pos);
x[pos] = val;
update(root, pos);
}
return calc_ans();
}
int updateY(int pos, int val) {
y[pos] = val;
update(root, pos);
return calc_ans();
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'int mul(int, int)':
horses.cpp:13:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
13 | return (long long) a * b % 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... |