| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 62302 |
2018-07-28T04:12:48 Z |
nvmdava |
Horses (IOI15_horses) |
C++17 |
|
1094 ms |
525312 KB |
#include "horses.h"
#include <bits/stdc++.h>
#define SIZE 500100
#define INF 1<<30
#define MOD 1000000007
using namespace std;
long long mult[SIZE * 3];
int maxLoc[SIZE * 3];
long double lazy[SIZE * 3], A[SIZE], maxValue[SIZE * 3];
int X[SIZE], Y[SIZE], N;
void update(int id, int l, int r, int k){
if(l == k && r == k){
mult[id] = X[l];
return;
}
int m = (l + r) >> 1;
if(m >= k){
update(id << 1, l, m, k);
} else {
update(id << 1 | 1, m + 1, r, k);
}
mult[id] = mult[id << 1] * mult[id << 1 | 1] % MOD;
}
void add(int id,int l, int r,int L,int R, long double diff){
if(l == L && r == R){
maxValue[id] += diff;
lazy[id] += diff;
return;
}
if(lazy[id] != 0){
lazy[id << 1] +=lazy[id];
lazy[id << 1 | 1] +=lazy[id];
maxValue[id << 1] +=lazy[id];
maxValue[id << 1 | 1] +=lazy[id];
lazy[id] = 0;
}
int m = (l + r) >> 1;
if(R <= m){
add(id << 1, l, m, L, R, diff);
} else if(L > m){
add(id << 1 | 1,m + 1, r, L, R, diff);
} else {
add(id << 1, l, m, L, R, diff);
add(id << 1 | 1,m + 1, r, L, R, diff);
}
if(maxValue[id << 1] > maxValue[id << 1 | 1]){
maxValue[id] = maxValue[id << 1];
maxLoc[id] = maxLoc[id << 1];
} else {
maxValue[id] = maxValue[id << 1 | 1];
maxLoc[id] = maxLoc[id << 1 | 1];
}
}
long long solve(int id, int l, int r,int L,int R){
if(L == l && r == R){
return mult[id];
}
int m = (l + r) >> 1;
if(R <= m){
return solve( id << 2, l, m, L , R);
} else if(L > m){
return solve( id << 2 | 1, m + 1, r, L, R);
}
return solve( id << 2, l, m, L , R) * solve( id << 2 | 1, m + 1, r, L, R) % MOD;
}
void build(int id, int l, int r){
if(l == r){
maxLoc[id] = l;
mult[id] = X[l];
maxValue[id] = A[l];
return;
}
build(id << 1, l, (l + r) / 2);
build(id << 1 | 1, (l + r) / 2 + 1, r);
if(maxValue[id << 1] > maxValue[id << 1 | 1]){
maxLoc[id] = maxLoc[id << 1];
maxValue[id] = maxValue[id << 1];
} else {
maxLoc[id] = maxLoc[id << 1 | 1];
maxValue[id] = maxValue[id << 1 | 1];
}
mult[id] = mult[id << 1] * mult[id << 1 | 1] % MOD;
}
int init(int n, int XX[], int YY[]) {
N = n;
for(int i = 1; i <= N ; i++){
X[i] = XX[i - 1];
Y[i] = YY[i - 1];
}
for(int i = 1; i <= N; i++){
A[i] = A[i - 1] + log10(X[i]);
}
for(int i = 1; i <= N; i++){
A[i] += log10(Y[i]);
}
build(1,1,N);
return solve(1, 1, N , 1, maxLoc[1]) * Y[maxLoc[1]] % MOD;
}
int updateX(int pos, int val) {
pos++;
long double diff = log(val) - log(X[pos]);
X[pos] = val;
add(1, 1, N, pos, N, diff);
update(1, 1, N, pos);
return solve(1, 1, N, 1, maxLoc[1]) * Y[maxLoc[1]] % MOD;
return 0;
}
int updateY(int pos, int val) {
pos++;
long double diff = log(val) - log(Y[pos]);
Y[pos] = val;
add(1,1,N,pos,pos,diff);
return solve(1,1,N,1,maxLoc[1]) * Y[maxLoc[1]] % MOD;
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:111:54: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return solve(1, 1, N , 1, maxLoc[1]) * Y[maxLoc[1]] % MOD;
^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:121:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return solve(1, 1, N, 1, maxLoc[1]) * Y[maxLoc[1]] % MOD;
^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:131:49: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return solve(1,1,N,1,maxLoc[1]) * Y[maxLoc[1]] % MOD;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
1032 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1094 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
