| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1086313 |
2024-09-10T06:46:22 Z |
RiverFlow |
Horses (IOI15_horses) |
C++14 |
|
143 ms |
45964 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
const int N = (int)5e5 + 7;
const int mod = (int)1e9 + 7;
int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
int sub(int a, int b) { return a >= b ? a - b : a - b + mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int Pow(int a, long long b) {
int res = 1;
for(; b > 0; b >>= 1, a = 1ll * a * a % mod)
if (b & 1) res = 1ll * res * a % mod;
return res;
}
int n, x[N], y[N];
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define nl "\n"
#define ll long long
const ll LIM = (int)1e10;
struct ST {
int n;
vector<int> t;
ST () {};
ST (int _n) {
n = _n;
t.resize(4 * n + 7);
}
int comb(int a, int b) {
return y[a - 1] >= y[b - 1] ? a : b;
}
void build(int id, int l, int r) {
if (l == r) return void(t[id] = l);
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
t[id] = comb(t[id << 1], t[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v) {
if (l > v or r < u) return 0;
if (l >= u and r <= v) return t[id];
int m = (l + r) >> 1;
return comb(get(id << 1, l, m, u, v),
get(id << 1 | 1, m + 1, r, u, v));
}
int get(int l, int r) {
return get(1, 1, n, l + 1, r + 1);
}
void upd(int id, int l, int r, int p) {
if (l == r) return ;
int m = (l + r) >> 1;
if (p <= m)
upd(id << 1, l, m, p);
else
upd(id << 1 | 1, m + 1, r, p);
t[id] = comb(t[id << 1], t[id << 1 | 1]);
}
void upd(int p) {
upd(1, 1, n, p + 1);
}
};
struct FW {
int n;
vector<int> bit;
FW () {};
FW (int _n) {
n = _n;
bit.assign(n + 1, 1);
}
void build() {
FOR(i, 1, n) {
for(int j = i; j <= n; j += j & -j)
bit[j] = mul(bit[j], x[i - 1]);
}
}
void upd(int id, int v) {
++id;
for(; id <= n; id += id & -id)
bit[id] = mul(bit[id], v);
}
int get(int id) {
++id;
int res = 1;
for(; id > 0; id -= id & -id)
res = mul(res, bit[id]);
return res;
}
};
int fx() {
ll mx = 0;
int ans = 0;
FOD(i, n - 1, 0) {
if (y[i] >= mx) {
ans = i;
}
mx = max(mx, (ll)y[i]);
mx = min(LIM, mx * x[i]);
}
return ans;
}
set<int> posi; // left
vector<int> ones; // right
const int B = 30;
ST st;
FW fw;
int last_res = 0;
int calc() {
if (sz(ones) == 0) {
return y[ st.t[1] ];
}
vector<int> px;
bool ins = 0;
if (ones[0] > 0)
px.push_back(st.get(0, ones[0] - 1)), ins = 1;
for(int i = 0; i < sz(ones) - 1; ++i) {
px.push_back(st.get(ones[i], ones[i + 1] - 1));
}
px.push_back(st.get(ones.back(), n - 1));
ones.pop_back();
// co duoc vi tri max y roi
// co duoc cac px
// tim vi tri px nho nhat thoi
int ans = -1;
ll mx = 0;
FOD(j, sz(px) - 1, 0) {
int i = px[j] - 1;
if (y[i] >= mx) {
ans = i;
}
mx = max(mx, (ll)y[i]);
if (ins) {
if (j > 0)
mx = min(LIM, mx * x[ones[j - 1]]);
} else {
mx = min(LIM, mx * ones[j]);
}
}
// cerr << ans << nl;
// assert(ans != -1);
int t = fw.get(ans);
return mul(y[ans], t);
}
int init(int N, int X[], int Y[]) {
n = N;
FOR(i, 0, n - 1) x[i] = X[i], y[i] = Y[i];
st = ST(n);
fw = FW(n);
st.build(1, 1, n);
fw.build();
FOD(i, n - 1, 0) {
if (x[i] > 1) {
if (sz(ones) < B) ones.push_back(i);
else posi.insert(i);
}
}
reverse(ones.begin(), ones.end());
// for(int j : ones) cout << j << ' '; cout << nl;
return calc();
}
vector<int> nw;
int updateX(int pos, int val) {
// handle mot so viec tu >1, -> =1
if (x[pos] == val) return last_res;
if (sz(nw)) nw.clear();
if (x[pos] == 1) {
// vi tri dau tien ma pos >
if (sz(ones) == 0) {
ones.push_back(pos);
} else {
// size no lon hon 1
// xet vi tri dau tien no nho hon thoi
bool ins = 0;
FOR(i, 0, sz(ones) - 1) {
if (ones[i] > pos and !ins) {
nw.push_back(pos);
ins = 1;
}
nw.push_back(ones[i]);
}
if (!ins) nw.push_back(pos);
if (sz(nw) <= B) {
ones = nw;
} else {
reverse(all(ones));
posi.insert(ones.back());
ones.pop_back();
reverse(all(ones));
}
}
} else if (x[pos] > 1 and val == 1) {
// handle delete
if (posi.find(pos) != posi.end()) {
posi.erase(pos);
} else {
// nam trong day
if (sz(posi)) {
nw.push_back(*posi.rbegin());
posi.erase(*posi.rbegin());
}
FOR(i, 0, sz(ones) - 1) if (ones[i] != pos)
nw.push_back(ones[i]);
swap(nw, ones);
}
}
fw.upd(pos, mul(val, Pow(x[pos], mod - 2)));
x[pos] = val;
return calc();
}
int updateY(int pos, int val) {
y[pos] = val;
st.upd(pos);
return calc();
}
Compilation message
horses.cpp: In function 'int mul(int, int)':
horses.cpp:17:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
17 | int mul(int a, int b) { return 1LL * a * b % mod; }
| ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int Pow(int, long long int)':
horses.cpp:21:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
21 | for(; b > 0; b >>= 1, a = 1ll * a * a % mod)
| ~~~~~~~~~~~~^~~~~
horses.cpp:22:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
22 | if (b & 1) res = 1ll * res * a % mod;
| ~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:164:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
164 | int init(int N, int X[], int Y[]) {
| ~~~~^
horses.cpp:11:11: note: shadowed declaration is here
11 | const int N = (int)5e5 + 7;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
444 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
45964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
