| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 274209 | A02 | 말 (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
#include <iostream>
#include <math.h>
using namespace std;
long long prime = 1000000007;
long long mod_exp(long long a, long long k){
if (k == 0){
return 1;
}
if (k == 1){
return a;
}
long long a1 = mod_exp(a, k / 2);
if (k % 2 == 1){
return (((a1 * a1) % prime) * a) % prime;
}
return (a1 * a1) % prime;
}
void updateModSegTree(vector<long long> &tree, int p, long long t){
int N = tree.size() / 2;
tree[p + N] = (tree[p + N] * t) % prime;
for (p = (p + N) / 2; p > 0; p = p / 2){
tree[p] = (tree[2 * p] * tree[2 * p + 1]) % prime;
}
}
long long queryModSegTree(vector<long long> &tree, int l, int r){
int N = tree.size() / 2;
long long total = 1;
for (l += N, r += N; l < r; l /= 2, r /= 2){
if (l % 2 == 1){
total = (total * tree[l++]) % prime;
}
if (r % 2 == 1){
total = (total * tree[--r]) % prime;
}
}
return total;
}
void apply(vector<long double> &tree, vector<long double> &delayed, int p, long double t){
tree[p] += t;
if (p < delayed.size()){
delayed[p] += t;
}
}
void build(vector<long double> &tree, vector<long double> &delayed, int p, vector<int> &answer_node){
while (p > 1){
p /= 2;
answer_node[p] = answer_node[2 * p + 1];
if (tree[2 * p] > tree[2 * p + 1]){
answer_node[p] = answer_node[2 * p];
}
tree[p] = max(tree[2 * p], tree[2 * p + 1]) + delayed[p];
}
}
void push(vector<long double> &tree, vector<long double> &delayed, int p){
int N = tree.size() / 2;
int h = sizeof(int) * 8 - __builtin_clz(N);
for (int s = h; s > 0; s--){
int i = p >> s;
if (delayed[i] != 0){
apply(tree, delayed, 2 * i, delayed[i]);
apply(tree, delayed, 2 * i + 1, delayed[i]);
delayed[i] = 0;
}
}
}
void updateMaxSegTree(vector<long double> &tree, vector<long double> &delayed, int l, int r, long double t, vector<int> &answer_node){
int n = tree.size() / 2;
l += n;
r += n;
int L = l;
int R = r;
for (; l < r; l/=2, r/=2){
if (l % 2 == 1){
apply(tree, delayed, l++, t);
}
if (r % 2 == 1){
apply(tree, delayed, --r, t);
}
}
build(tree, delayed, L, answer_node);
build(tree, delayed, R - 1, answer_node);
}
int queryMaxSegTree(vector<long double> &tree, vector<long double> &delayed, int l, int r, vector<int> &answer_node){
int N = tree.size() / 2;
l += N;
r += N;
push(tree, delayed, l);
push(tree, delayed, r - 1);
long double answer = -1;
int answer_n = -1;
for (; l < r; l /= 2, r /= 2){
if (l % 2 == 1){
if (tree[l] > answer){
answer_n = answer_node[l];
}
answer = max(answer, tree[l++]);
}
if (r % 2 == 1){
if (tree[r - 1] > answer){
answer_n = answer_node[r - 1];
}
answer = max(answer, tree[--r]);
}
}
//cout << answer << endl;
return answer_n;
}
vector<long long> mod_seg_tree;
vector<long double> max_seg_tree;
vector<long double> max_seg_tree_delayed;
vector<int> answer_node;
vector<long long> Xi;
vector<long long> Yi;
int init(int N, int X[], int Y[]) {
mod_seg_tree = vector<long long> (2 * N, 1);
max_seg_tree = vector<long double> (2 * N, 0.0);
max_seg_tree_delayed = vector<long double> (N, 0.0);
answer_node = vector<int> (2 * N, 0);
for (int i = 0; i < N; i++){
answer_node[i + N] = i;
Xi.push_back(X[i]);
Yi.push_back(Y[i]);
}
for (int i = 0; i < N; i++){
//cout << i << ' ' << X[i] << endl;
updateModSegTree(mod_seg_tree, i, X[i]);
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, N, log((long double) X[i]), answer_node);
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, i + 1, log((long double) Y[i]), answer_node);
}
int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
//cout << best << endl;
long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
//cout << 'a' << endl;
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
return (answer * Yi[best]) % prime;
}
int updateX(int pos, int val) {
// int N = max_seg_tree.size() / 2;
// updateModSegTree(mod_seg_tree, pos, val * mod_exp(Xi[pos], prime - 1));
// updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, pos, N, log((long double) val) - log((long double) Xi[pos]), answer_node);
Xi[pos] = val;
// int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
// //cout << best << endl;
// long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
// //cout << 'a' << endl;
// //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
// return ((answer * Yi[best]) % prime);
mod_seg_tree = vector<long long> (2 * N, 1);
max_seg_tree = vector<long double> (2 * N, 0.0);
max_seg_tree_delayed = vector<long double> (N, 0.0);
answer_node = vector<int> (2 * N, 0);
for (int i = 0; i < N; i++){
//cout << i << ' ' << X[i] << endl;
updateModSegTree(mod_seg_tree, i, X[i]);
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, N, log((long double) X[i]), answer_node);
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, i + 1, log((long double) Y[i]), answer_node);
}
int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
//cout << best << endl;
long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
//cout << 'a' << endl;
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
return (answer * Yi[best]) % prime;
}
int updateY(int pos, int val) {
// int N = max_seg_tree.size() / 2;
// updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, pos, pos + 1, log((long double) val) - log((long double) Yi[pos]), answer_node);
Yi[pos] = val;
// int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
// //cout << best << endl;
// long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
// //cout << 'a' << endl;
// //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
// return ((answer * Yi[best]) % prime);
mod_seg_tree = vector<long long> (2 * N, 1);
max_seg_tree = vector<long double> (2 * N, 0.0);
max_seg_tree_delayed = vector<long double> (N, 0.0);
answer_node = vector<int> (2 * N, 0);
for (int i = 0; i < N; i++){
//cout << i << ' ' << X[i] << endl;
updateModSegTree(mod_seg_tree, i, X[i]);
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, N, log((long double) X[i]), answer_node);
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, i + 1, log((long double) Y[i]), answer_node);
}
int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
//cout << best << endl;
long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
//cout << 'a' << endl;
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
return (answer * Yi[best]) % prime;
}