# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
126405 | KieranHorgan | 말 (IOI15_horses) | C++17 | 61 ms | 25096 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
#define ll long long
int n;
vector<int> Y_;
vector<int> X_;
vector<ll> st;
ll op(ll a, ll b) {
return (a*b)%MOD;
}
void build(int id = 1, int l = 0, int r = n) {
if(l+1==r) {
st[id] = X_[l];
return;
}
int mid = (l+r)>>1;
build(id<<1, l, mid);
build((id<<1) | 1, mid, r);
st[id] = op(st[id<<1], st[(id<<1)|1]);
return;
}
void update(int pos, int val, int id = 1, int l = 0, int r = n) {
if(pos >= r || pos < l) return;
if(l+1 == r) {
X_[pos] = val;
st[id] = val;
return;
}
int mid = (l+r)/2;
update(pos, val, id<<1, l, mid);
update(pos, val, (id<<1)|1, mid, r);
st[id] = op(st[id<<1], st[(id<<1)|1]);
}
int query(int pos, int id = 1, int l = 0, int r = n) {
if(pos >= r-1) return st[id];
if(pos < l) return 1;
int mid = (l+r)/2;
return op(query(pos, id<<1, l, mid),
query(pos, (id<<1)|1, mid, r));
}
int calcBestPos() {
int i = max(0, n-20);
int curBest = Y_[i];
int curBestPos = i;
int run = X_[i];
for(i++; i < n; i++) {
if(run * Y_[i] * X_[i] >= curBest) {
run = 1;
curBest = Y_[i] * X_[i];
curBestPos = i;
} else {
run *= X_[i];
}
}
return curBestPos;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i = 0; i < n; i++) {
X_.push_back(X[i]);
Y_.push_back(Y[i]);
}
st.resize(3*n+5);
build();
int p = calcBestPos();
return op(query(p), Y_[p]);
}
int updateX(int pos, int val) {
update(pos,val);
int p = calcBestPos();
return op(query(p), Y_[p]);
}
int updateY(int pos, int val) {
Y_[pos] = val;
int p = calcBestPos();
return op(query(p), Y_[p]);
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |