| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 823416 |
2023-08-12T13:37:17 Z |
_martynas |
Horses (IOI15_horses) |
C++11 |
|
348 ms |
40492 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#warning change mxn
const int mxn = 5e5+5;
const int mxval = 1e9;
const int mod = 1e9+7;
struct Seg {
int mx[4*mxn];
int get(int u, int l, int r, int ql, int qr) {
if(qr < l || r < ql) return 0;
if(ql <= l && r <= qr) return mx[u];
int m = (l+r)/2;
return max(get(2*u, l, m, ql, qr), get(2*u+1, m+1, r, ql, qr));
}
void set(int u, int l, int r, int i, int x) {
if(l == r) {
mx[u] = x; return;
}
int m = (l+r)/2;
if(i <= m) set(2*u, l, m, i, x);
else set(2*u+1, m+1, r, i, x);
mx[u] = max(mx[2*u], mx[2*u+1]);
}
} seg;
int n;
int x[mxn], y[mxn];
set<int> st;
ll tot = 1;
ll mod_pow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans*a%mod;
a = a*a%mod;
b >>= 1;
}
return ans;
}
int init(int N, int X[], int Y[]) {
n = N;
copy(X, X+n, x); copy(Y, Y+n, y);
for(int i = 0; i < N; i++) seg.set(1, 0, n-1, i, Y[i]);
st.insert(n-1);
tot = X[n-1];
for(int i = n-2; i >= 0; i--) {
if(X[i] > 1) {
tot = tot*X[i]%mod;
st.insert(i);
}
}
return 0;
}
int get() {
ll acc = 1;
int last = -1;
auto rit = st.rbegin();
while(rit != st.rend()) {
acc *= x[*rit];
last = *rit;
if(acc > mxval) break;
rit = next(rit);
}
auto it = st.lower_bound(last);
int prev = acc > mxval ? last : 0;
ll mx = 0; acc = 1;
while(it != st.end()) {
int i = *it;
ll best_y = seg.get(1, 0, n-1, prev, i);
if(i != last) acc = acc*x[i];
mx = max(mx, acc*best_y);
prev = i+1;
it = next(it);
}
//printf("mx = %lld\n", mx);
mx %= mod;
return tot*mod_pow(acc, mod-2)%mod*mx%mod;
}
int updateX(int pos, int val) {
tot = tot*mod_pow(x[pos], mod-2)%mod;
x[pos] = val;
tot = tot*val%mod;
if(val > 1 || pos == n-1) st.insert(pos);
else (st.erase(pos));
return get();
}
int updateY(int pos, int val) {
seg.set(1, 0, n-1, pos, val);
return get();
}
// int main(int argc, char const *argv[])
// {
// int N;
// cin >> N;
// int X[N], Y[N];
// for(int i = 0; i < N; i++) cin >> X[i];
// for(int i = 0; i < N; i++) cin >> Y[i];
// init(N, X, Y);
// int M;
// cin >> M;
// for(int i = 0; i < M; i++) {
// int type; cin >> type;
// int pos, val; cin >> pos >> val;
// if(type == 1) {
// cout << "resp: " << updateX(pos, val) << "\n";
// }
// else {
// cout << "resp: " << updateY(pos, val) << "\n";
// }
// }
// return 0;
// }
Compilation message
horses.cpp:8:2: warning: #warning change mxn [-Wcpp]
8 | #warning change mxn
| ^~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:84:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
84 | return tot*mod_pow(acc, mod-2)%mod*mx%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
348 ms |
40492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
