| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 789474 |
2023-07-21T12:30:29 Z |
Blagoj |
Horses (IOI15_horses) |
C++17 |
|
419 ms |
72668 KB |
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
ll n, x[1500000], y[1500000], mod = 1e9 + 7;
struct SegmentTree {
vector<ll> mul;
vector<pair<ll, ll>> mx;
void init() {
mx.resize(n * 3, {0, 0});
mul.resize(n * 3, 1);
}
void build(int k, int l, int r) {
if (l == r) {
mx[k] = { y[l], l };
mul[k] = x[l];
return;
}
build(k * 2, l, (l + r) / 2);
build(k * 2 + 1, (l + r) / 2 + 1, r);
mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
}
void update(int k, int l, int r, int i, ll v, bool t) {
if (l > i || r < i) return;
if (l == r) {
if (!t) mx[k].first = v;
else mul[k] = v;
return;
}
update(k * 2, l, (l + r) / 2, i, v, t);
update(k * 2 + 1, (l + r) / 2 + 1, r, i, v, t);
mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
mul[k] = (mul[k * 2] * mul[k * 2 + 1]) % mod;
}
ll getX(int k, int l, int r, int i, int j) {
if (l > j || r < i) return 1;
if (i <= l && r <= j) return mul[k];
return (getX(k * 2, l, (l + r) / 2, i, j) * getX(k * 2 + 1, (l + r) / 2 + 1, r, i, j)) % mod;
}
pair<ll, ll> getY(int k, int l, int r, int i, int j) {
if (l > j || r < i) return {0, 0};
if (i <= l && r <= j) return mx[k];
return max( getY(k * 2, l, (l + r) / 2, i, j), getY(k * 2 + 1, (l + r) / 2 + 1, r, i, j) );
}
} sgt;
set<int> s;
ll solve() {
auto itf = --s.end(), its = --s.end();
itf--;
ll val = -1, id = n;
for (int i = 0; i < 32 && its != s.begin(); i++) {
pair<ll, ll> t = sgt.getY(1, 0, n - 1, *itf, *its - 1);
if (t.first > val) {
val = t.first;
id = t.second;
}
val *= x[*itf];
if (val > 2e9 || itf == s.begin()) break;
its--;
itf--;
}
return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < N; i++) {
x[i] = X[i], y[i] = Y[i];
if (x[i] != 1) s.insert(i);
}
s.insert(0);
s.insert(n);
sgt.init();
sgt.build(1, 0, n - 1);
return solve();
}
int updateX(int pos, int val) {
if (x[pos] != 1 && pos != 0) s.erase(pos);
x[pos] = val;
sgt.update(1, 0, n - 1, pos, val, 1);
if (val != 1) s.insert(pos);
return solve();
}
int updateY(int pos, int val) {
y[pos] = val;
sgt.update(1, 0, n - 1, pos, val, 0);
return solve();
}
Compilation message
horses.cpp: In function 'long long int solve()':
horses.cpp:65:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
65 | pair<ll, ll> t = sgt.getY(1, 0, n - 1, *itf, *its - 1);
| ~~^~~
horses.cpp:71:7: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
71 | if (val > 2e9 || itf == s.begin()) break;
| ^~~
horses.cpp:75:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
75 | return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
| ~~^~~
horses.cpp:75:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
75 | return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
| ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:85:11: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
85 | s.insert(n);
| ^
horses.cpp:87:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
87 | sgt.build(1, 0, n - 1);
| ~~^~~
horses.cpp:88:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
88 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:94:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
94 | sgt.update(1, 0, n - 1, pos, val, 1);
| ~~^~~
horses.cpp:96:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
96 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:101:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
101 | sgt.update(1, 0, n - 1, pos, val, 0);
| ~~^~~~
horses.cpp:102:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
102 | return solve();
| ~~~~~^~
| # |
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 |
0 ms |
308 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
419 ms |
72668 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 |
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 |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
