| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 653654 |
2022-10-27T14:32:09 Z |
esomer |
Horses (IOI15_horses) |
C++17 |
|
835 ms |
40788 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const int MOD = 1e9 + 7;
const int maxN = 500000;
const int siz = 1048576;
int N;
int x[maxN];
int y[maxN];
int segTree[siz];
int segTree2[siz];
set<int> s;
void st(int i, int v, int x, int lx, int rx){
if(rx - lx == 1){
segTree[x] = v;
return;
}
int m = (lx + rx) / 2;
if(i < m) st(i, v, 2 * x + 1, lx, m);
else st(i, v, 2 * x + 2, m, rx);
segTree[x] = max(segTree[2 * x + 1], segTree[2 * x + 2]);
}
int mx(int l, int r, int x, int lx, int rx){
if(lx >= l && rx <= r) return segTree[x];
else if(lx >= r || rx <= l) return 0;
int m = (lx + rx) / 2;
int m1 = mx(l, r, 2 * x + 1, lx, m);
int m2 = mx(l, r, 2 * x + 2, m, rx);
return max(m1, m2);
}
void st_x(int i, int v, int x, int lx, int rx){
if(rx - lx == 1){
segTree2[x] = v;
return;
}
int m = (lx + rx) / 2;
if(i < m) st_x(i, v, 2 * x + 1, lx, m);
else st_x(i, v, 2 * x + 2, m, rx);
ll left = segTree2[2 * x + 1];
ll right = segTree2[2 * x + 2];
segTree2[x] = (left * right) % MOD;
}
ll mult(int l, int r, int x, int lx, int rx){
if(lx >= l && rx <= r) return segTree2[x];
else if(lx >= r || rx <= l) return 1;
int m = (lx + rx) / 2;
ll m1 = mult(l, r, 2 * x + 1, lx, m);
ll m2 = mult(l, r, 2 * x + 2, m, rx);
return (m1 * m2) % MOD;
}
int ans(){
vector<int> ind;
ll best = 0;
ll optimaly = -1;
int r;
if(s.empty() == false){
auto it = s.end();
it--;
ll curr = 1;
bool included = 0;
while(curr <= 1e9){
//cout << "Curr "<< curr << " *it "<< *it << endl;
curr *= x[*it];
ind.push_back(*it);
if(curr > 1e9) continue;
if(*it == 0) included = 1;
if(it != s.begin()) it--;
else{
if(*it != 0) ind.push_back(0);
break;
}
}
reverse(ind.begin(), ind.end());
curr = 1;
if(included) curr = x[0];
ind.push_back(N);
/*for(int l : ind) cout << l << " ";
cout << endl;*/
for(int i = 1; i < ind.size(); i++){
ll bestY = mx(ind[i - 1], ind[i], 0, 0, siz);
//cout << "I: "<< i << " bestY "<< bestY << endl;
if(best < curr * bestY){
optimaly = bestY;
best = curr * bestY;
r = i;
}
curr *= x[ind[i]];
}
}else{
//cout << "Here"<< endl;
ind.push_back(N);
r = 0;
optimaly = mx(0, N, 0, 0, siz);
}
return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
}
int init(int n, int X[], int Y[] /*vector<int> X, vector<int> Y*/) {
N = n;
for(int i = 0; i < siz; i++){
segTree[i] = 0; segTree2[i] = 1;
}
for(int i = 0; i < N; i++){
x[i] = X[i]; y[i] = Y[i];
st(i, y[i], 0, 0, siz);
st_x(i, x[i], 0, 0, siz);
if(x[i] != 1) s.insert(i);
}
return ans();
}
int updateX(int pos, int val) {
st_x(pos, val, 0, 0, siz);
if(x[pos] != 1 && val == 1) s.erase(pos);
else if(x[pos] == 1 && val != 1) s.insert(pos);
x[pos] = val;
return ans();
}
int updateY(int pos, int val) {
st(pos, val, 0, 0, siz);
return ans();
}
/*
int main() {
int n; cin >> n;
vector<int> v(n);
vector<int> v2(n);
for(auto &i : v) cin >> i;
for(auto &i : v2) cin >> i;
cout << init(n, v, v2) << endl;
int m; cin >> m;
while(m--){
int t, pos, val; cin >> t >> pos >> val;
if(t) cout << updateX(pos, val) << endl;
else cout << updateY(pos, val)<< endl;
}
}*/
Compilation message
horses.cpp: In function 'void st(int, int, int, int, int)':
horses.cpp:18:27: warning: declaration of 'x' shadows a global declaration [-Wshadow]
18 | void st(int i, int v, int x, int lx, int rx){
| ~~~~^
horses.cpp:12:5: note: shadowed declaration is here
12 | int x[maxN];
| ^
horses.cpp: In function 'int mx(int, int, int, int, int)':
horses.cpp:29:26: warning: declaration of 'x' shadows a global declaration [-Wshadow]
29 | int mx(int l, int r, int x, int lx, int rx){
| ~~~~^
horses.cpp:12:5: note: shadowed declaration is here
12 | int x[maxN];
| ^
horses.cpp: In function 'void st_x(int, int, int, int, int)':
horses.cpp:38:29: warning: declaration of 'x' shadows a global declaration [-Wshadow]
38 | void st_x(int i, int v, int x, int lx, int rx){
| ~~~~^
horses.cpp:12:5: note: shadowed declaration is here
12 | int x[maxN];
| ^
horses.cpp:48:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
48 | segTree2[x] = (left * right) % MOD;
| ~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'long long int mult(int, int, int, int, int)':
horses.cpp:51:27: warning: declaration of 'x' shadows a global declaration [-Wshadow]
51 | ll mult(int l, int r, int x, int lx, int rx){
| ~~~~^
horses.cpp:12:5: note: shadowed declaration is here
12 | int x[maxN];
| ^
horses.cpp: In function 'int ans()':
horses.cpp:70:15: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
70 | while(curr <= 1e9){
| ^~~~
horses.cpp:74:16: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
74 | if(curr > 1e9) continue;
| ^~~~
horses.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 1; i < ind.size(); i++){
| ~~^~~~~~~~~~~~
horses.cpp:104:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
104 | return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:104:34: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
104 | return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8404 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8480 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8508 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
835 ms |
40788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8532 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8468 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
