# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
58490 |
2018-07-18T03:25:53 Z |
E869120 |
Horses (IOI15_horses) |
C++14 |
|
1500 ms |
19400 KB |
#include "horses.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class RangeMax {
public:
vector<int>dat; int size_ = 0;
void init(int sz) {
size_ = 1;
while (size_ <= sz) size_ *= 2;
dat.resize(size_ * 2, 0);
}
void update(int p, int x) {
p += size_; dat[p] = x; p >>= 1;
while (p >= 1) { dat[p] = max(dat[p * 2], dat[p * 2 + 1]); p >>= 1; }
}
int getmax_(int l, int r, int a, int b, int u) {
if (b <= l || r <= a) return -1;
if (l <= a && b <= r) return dat[u];
return max(getmax_(l, r, a, (a + b) >> 1, u * 2), getmax_(l, r, (a + b) >> 1, b, u * 2 + 1));
}
int getmax(int l, int r) {
return getmax_(l, r, 0, size_, 1);
}
};
int bit[500009];
void add(int pos, int x) {
pos++;
while (pos < 500009) { bit[pos] += x; pos += (pos&-pos); }
}
int sum(int pos) {
int s = 0; pos++;
while (pos >= 1) { s += bit[pos]; pos -= (pos&-pos); }
return s;
}
long long N, X[500009], Y[500009], Allval = 0, mod = 1000000007;
RangeMax Q;
long long modpow(long long a, long long b, long long m) {
long long p = 1, q = a;
for (int i = 0; i < 31; i++) {
if ((b&(1LL << i)) != 0) { p *= q; p %= m; }
q *= q; q %= m;
}
return p;
}
long long Div(long long a, long long b, long long m) {
return (1LL * a*modpow(b, m - 2, m)) % m;
}
int solve() {
pair<int, int>maxid = make_pair(0, 1);
long long P = 1, cx = N - 1;
while (true) {
// 二分探索 Phase
long long M = 0, I = sum(cx), J = 0;
for (int i = 17; i >= 0; i--) {
if (bit[M + (1 << i)] + J < I) M += (1 << i);
}
M--;
// 結果を求める Phase
long long YY = Q.getmax(M, cx + 1);
if (maxid.first * P < maxid.second * YY) maxid = make_pair(YY, P);
P *= X[M]; cx = M - 1;
if (P > (1LL << 30) || cx < 0) break;
}
long long J = Div(Allval, maxid.second, mod);
J *= maxid.first; J %= mod;
return J;
}
int init(int NN, int XX[], int YY[]) {
N = NN; Allval = 1; Q.init(N + 2);
for (int i = 0; i < N; i++) { X[i] = XX[i]; Allval *= X[i]; Allval %= mod; if (X[i] >= 2) add(i, 1); }
for (int i = 0; i < N; i++) { Y[i] = YY[i]; Q.update(i, Y[i]); }
return solve();
}
int updateX(int pos, int val) {
Allval = Div(Allval, X[pos], mod); if (X[pos] >= 2) add(pos, -1);
X[pos] = val;
Allval *= X[pos]; Allval %= mod; if (X[pos] >= 2) add(pos, 1);
return solve();
}
int updateY(int pos, int val) {
Y[pos] = val; Q.update(pos, Y[pos]);
return solve();
}
Compilation message
horses.cpp: In function 'int solve()':
horses.cpp:62:30: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
long long M = 0, I = sum(cx), J = 0;
^
horses.cpp:69:36: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
long long YY = Q.getmax(M, cx + 1);
^
horses.cpp:69:33: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
long long YY = Q.getmax(M, cx + 1);
~~~^~~
horses.cpp:77:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return J;
^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:81:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
N = NN; Allval = 1; Q.init(N + 2);
~~^~~
horses.cpp:83:61: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
for (int i = 0; i < N; i++) { Y[i] = YY[i]; Q.update(i, Y[i]); }
~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:95:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
Y[pos] = val; Q.update(pos, Y[pos]);
~~~~~^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Execution timed out |
1569 ms |
548 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
548 KB |
Output is correct |
2 |
Execution timed out |
1567 ms |
548 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
817 ms |
19400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
19400 KB |
Output is correct |
2 |
Execution timed out |
1573 ms |
19400 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
19400 KB |
Output is correct |
2 |
Execution timed out |
1577 ms |
19400 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |