이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#define MAX 50000
#define ll long long
#define lft 2 * v
#define rht (2 * v) + 1
ll MOD = 1e9 + 7;
using namespace std;
ll n;
ll y[MAX];
ll x[MAX];
vector<ll> seg_prod(MAX * 4);
vector<ll> seg_prod_max(MAX * 4);
vector<ll> seg_y(MAX * 4);
void build(ll v, ll tl, ll tr) {
if (tl == tr) {
seg_prod[v] = x[tl];
seg_prod_max[v] = x[tl];
} else {
ll mid = (tl + tr) / 2;
build(lft, tl, mid);
build(rht, mid + 1, tr);
seg_prod[v] = (seg_prod[lft] * seg_prod[rht]) % MOD;
seg_prod_max[v] = min(seg_prod_max[lft] * seg_prod_max[rht], MOD);
}
}
void update(ll v, ll idx, ll tl, ll tr) {
if (tl > tr) return;
if (tl == idx && tl == tr) {
seg_prod[v] = x[idx];
seg_prod_max[v] = x[idx];
return;
}
ll mid = (tl + tr) / 2;
if (idx > mid) update(rht, idx, mid + 1, tr);
else update(lft, idx, tl, mid);
seg_prod[v] = (seg_prod[lft] * seg_prod[rht]) % MOD;
seg_prod_max[v] = min(seg_prod_max[lft] * seg_prod_max[rht], MOD);
}
ll query1(ll v, ll l, ll r, ll tl, ll tr) {
if (l > r) return 1;
if (tl == l && tr == r) return seg_prod[v];
ll mid = (tl + tr) / 2;
ll ret = query1(lft, l, min(r, mid), tl, mid) *
query1(rht, max(l, mid + 1), r, mid + 1, tr);
return ret % MOD;
}
ll query2(ll v, ll l, ll r, ll tl, ll tr) {
if (l > r) return 1;
if (tl == l && tr == r) return seg_prod_max[v];
ll mid = (tl + tr) / 2;
ll ret = query2(lft, l, min(r, mid), tl, mid) *
query2(rht, max(l, mid + 1), r, mid + 1, tr);
return min(MOD, ret);
}
void build_y(ll v, ll tl, ll tr) {
if (tl == tr) seg_y[v] = tl;
else {
ll mid = (tl + tr) / 2;
build_y(lft, tl, mid);
build_y(rht, mid + 1, tr);
ll left = seg_y[lft];
ll right = seg_y[rht];
ll p1 = y[left]; ll p2 = query2(1, left + 1, right, 0, n - 1) * y[right];
if (p2 > p1) seg_y[v] = right;
else seg_y[v] = left;
}
}
void update_y(ll v, ll idx, ll tl, ll tr) {
if (tl > tr) return;
if (tl == tr && tl == idx) {
seg_y[v] = idx;
return;
}
ll mid = (tl + tr) / 2;
if (idx > mid) update_y(rht, idx, mid + 1, tr);
else update_y(lft, idx, tl, mid - 1);
ll left = seg_y[lft];
ll right = seg_y[rht];
ll p1 = y[left]; ll p2 = query2(1, left + 1, right, 0, n - 1);
if (p2 > p1) seg_y[v] = right;
else seg_y[v] = left;
}
ll find() {
return (query1(1, 0, seg_y[1], 0, n - 1) * y[seg_y[1]]) % MOD;
}
int init(int N, int X[], int Y[]) {
n = (ll)N;
for (ll i = 0; i < n; ++i) y[i] = (ll)Y[i];
for (ll i = 0; i < n; ++i) x[i] = (ll)X[i];
build(1, 0, n - 1);
build_y(1, 0, n - 1);
return find();
}
int updateX(int pos, int val) {
x[pos] = val;
update(1, pos, 0, n - 1);
update_y(1, pos, 0, n - 1);
return find();
}
int updateY(int pos, int val) {
y[pos] = val;
update_y(1, pos, 0, n - 1);
return find();
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:116:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:129:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
# | 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... |