| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 795162 |
2023-07-27T07:12:43 Z |
iee |
Horses (IOI15_horses) |
C++17 |
|
138 ms |
94224 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5, P = 1e9 + 7;
using ld = long double;
struct info {
ld lo;
int mo;
explicit info() = default;
info(ld _lo, int _mo) : lo(_lo), mo(_mo) {
}
friend info operator *(const info &p, const info &q) {
return {p.lo + q.lo, (int) (1LL * p.mo * q.mo % P)};
}
friend bool operator <(const info &p, const info &q) {
return pair{p.lo, p.mo} < pair{q.lo, q.mo};
}
} tr[N << 2], I{log(1), 1}, lazy[N << 2], ini[N];
vector<int> X, Y;
int n;
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1LL * res * a % P;
a = 1LL * a * a % P;
b /= 2;
}
return res;
}
void build(int u, int l, int r) {
lazy[u] = I;
if (l == r) {
tr[u] = ini[l];
return;
}
const int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
}
void spread(int u) {
info &ta = lazy[u];
tr[u << 1] = tr[u << 1] * ta, lazy[u << 1] = lazy[u << 1] * ta;
tr[u << 1 | 1] = tr[u << 1 | 1] * ta, lazy[u << 1 | 1] = lazy[u << 1 | 1] * ta;
ta = I;
}
void mul(int u, int ql, int qr, int l, int r, info val) {
if (l >= ql && r <= qr) {
lazy[u] = lazy[u] * val;
tr[u] = tr[u] * val;
return;
}
spread(u);
const int mid = (l + r) >> 1;
if (ql <= mid) mul(u << 1, ql, qr, l, mid, val);
if (qr > mid) mul(u << 1 | 1, ql, qr, mid + 1, r, val);
tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
}
int init(int N, int XX[], int YY[]) {
n = N, X = vector(XX, XX + n), Y = vector(YY, YY + n);
for (int i = 0; i < n; i++) {
ini[i].lo = log(X[i]);
if (i) ini[i].lo += ini[i - 1].lo;
}
for (int i = 0; i < n; i++) {
ini[i].lo += log(Y[i]);
}
for (int i = 0; i < n; i++) {
ini[i].mo = X[i];
if (i) ini[i].mo = 1LL * ini[i - 1].mo % P;
}
for (int i = 0; i < n; i++) {
ini[i].mo = 1LL * ini[i].mo * Y[i] % P;
}
build(1, 0, n - 1);
return tr[1].mo;
}
int updateX(int pos, int val) {
info mu{log(val) - log(X[pos]), (int) (1LL * val * qpow(X[pos], P - 2) % P)};
X[pos] = val;
mul(1, pos, n - 1, 0, n - 1, mu);
return tr[1].mo;
}
int updateY(int pos, int val) {
info mu{log(val) - log(Y[pos]), (int) (1LL * val * qpow(Y[pos], P - 2) % P)};
Y[pos] = val;
mul(1, pos, pos, 0, n - 1, mu);
return tr[1].mo;
}
Compilation message
horses.cpp: In function 'int qpow(int, int)':
horses.cpp:24:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
24 | if (b & 1) res = 1LL * res * a % P;
| ~~~~~~~~~~~~~~^~~
horses.cpp:25:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
25 | a = 1LL * a * a % P;
| ~~~~~~~~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:58:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
58 | int init(int N, int XX[], int YY[]) {
| ~~~~^
horses.cpp:4:15: note: shadowed declaration is here
4 | constexpr int N = 5e5 + 5, P = 1e9 + 7;
| ^
horses.cpp:72:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
72 | ini[i].mo = 1LL * ini[i].mo * Y[i] % P;
| ~~~~~~~~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
94224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
