#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int NMAX = 5e5, modulo = 1e9 + 7;
int n, x[NMAX + 5], y[NMAX + 5], tree[4*NMAX + 5], tree2[4*NMAX + 5];
set<pair<int, int>> pos;
int combine(int a, int b) { return y[a] > y[b] ? a : b; }
void update(int v, int tl, int tr, int k) {
if(tl == tr) tree[v] = k;
else {
int tm = (tl + tr)/2;
if(k <= tm) update(v*2, tl, tm, k);
else update(v*2 + 1, tm + 1, tr, k);
tree[v] = combine(tree[v*2], tree[v*2 + 1]);
}
}
int query(int v, int tl, int tr, int l, int r) {
if(l >r) return 0;
else if (tl == l && tr == r) return tree[v];
else {
int tm = (tl + tr)/2;
return combine(query(v*2, tl, tm, l, min(tm, r)), query(v*2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
}
void update2(int v, int tl, int tr, int k, int x) {
if (tl == tr) tree2[v] = x;
else {
int tm = (tl + tr)/2;
if (k <= tm) update2(v*2, tl, tm, k, x);
else update2(v*2 + 1, tm + 1, tr, k, x);
tree2[v] = (tree2[v*2]*tree2[v*2 + 1]) % modulo;
}
}
int query2(int v, int tl, int tr, int l, int r) {
if (l > r) return 1;
else if (tl == l&& tr == r) return tree2[v];
else {
int tm = (tl+ tr)/2;
return (query2(v*2, tl, tm, l, min(tm, r))*query2(v*2 + 1, tm + 1, tr, max(l, tm + 1), r)) % modulo;
}
}
void merge(int index) {
if (x[index] != 1) { pos.insert({index, index}); return; }
auto rig = pos.upper_bound({index, -1e9}), lef = rig; lef--;
bool l1 = x[index - 1] == 1, r1 = x[index + 1] == 1;
pair<int, int> lp = *lef, rp = *rig;
if (lp.second + 1 == index && index + 1 == rp.first && l1 && r1) pos.erase(lef), pos.erase(rig), pos.insert({lp.first, rp.second});
else if (lp.second + 1 == index && l1) pos.erase(lef), pos.insert({lp.first, index});
else if (index + 1 == rp.first && r1) pos.erase(rig), pos.insert({index, rp.second});
else pos.insert({index, index});
}
void split(int index) {
auto it = pos.upper_bound({index, -1e9}); it--;
pair<int, int> p = *it;
pos.erase(it);
if (p.first < index) pos.insert({p.first, index - 1});
if (index < p.second) pos.insert({index + 1, p.second});
}
int compute() {
auto it = pos.end(); it--, it--;
vector<int> res;
for (int cnt = 60; cnt && it != pos.begin(); it--, cnt--) {
int l = it->first, r = it->second;
int maxY = query(1, 1, n, l, r);
res.push_back(maxY);
}
int mx = 0;
for (int i = 1; i < res.size(); i++) {
int cur = y[res[mx]];
for (int j = mx; j <= i && cur <= y[res[i]]; j++) cur *= x[res[j]];
if (cur <= y[res[i]]) mx = i;
}
//for (int i = 0; i < res.size(); i++) cout << res[i] << " ";
//cout << '\n';
//for (auto&x : pos) cout << x.first << " " << x.second << '\n';
return (query2(1, 1, n, 1, res[mx])*y[res[mx]]) % modulo;
}
signed init(signed N, signed X[], signed Y[]) {
n = N;
for (int i = 1; i <= n; i++) x[i] = X[i - 1], y[i] = Y[i - 1];
pos.insert({-1, -1}), pos.insert({1e9, 1e9});
for (int i = 1; i <= n; i++) merge(i);
for (int i = 1; i <= n; i++) update(1, 1, n, i), update2(1, 1, n, i, x[i]);
return compute();
}
signed updateX(signed pos, signed val) {
pos++;
if (x[pos] == val) return compute();
split(pos);
x[pos] = val;
update2(1, 1, n, pos, x[pos]);
merge(pos);
return compute();
}
signed updateY(signed pos, signed val) {
pos++;
y[pos] = val;
update(1, 1, n, pos);
return compute();
}
/*signed main() {
//_inputFile = fopen("horses.in", "rb");
//_outputFile = fopen("horses.out", "w");
signed N;
cin >> N;
signed *X = (signed*)malloc(sizeof(signed)*(unsigned)N);
signed *Y = (signed*)malloc(sizeof(signed)*(unsigned)N);
for (int i = 0; i < N; i++) {
cin >> X[i];
}
for (int i = 0; i < N; i++) {
cin >> Y[i];
}
//fprintf(_outputFile,"%d\n",init(N,X,Y));
cout << init(N, X, Y) << '\n';
signed M;
cin >> M;
for (int i = 0; i < M; i++) {
signed type; cin >> type;
signed pos; cin >> pos;
signed val; cin >> val;
if (type == 1) {
//fprintf(_outputFile,"%d\n",updateX(pos,val));
cout << updateX(pos, val) << '\n';
} else if (type == 2) {
//fprintf(_outputFile,"%d\n",updateY(pos,val));
cout << updateY(pos, val) << '\n';
}
}
return 0;
}*/
Compilation message
horses.cpp: In function 'void update2(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:33:48: warning: declaration of 'x' shadows a global declaration [-Wshadow]
33 | void update2(int v, int tl, int tr, int k, int x) {
| ^
horses.cpp:9:8: note: shadowed declaration is here
9 | int n, x[NMAX + 5], y[NMAX + 5], tree[4*NMAX + 5], tree2[4*NMAX + 5];
| ^
horses.cpp: In function 'long long int compute()':
horses.cpp:80:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 1; i < res.size(); i++) {
| ~~^~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
97 | return compute();
| ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:100:23: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
100 | signed updateX(signed pos, signed val) {
| ~~~~~~~^~~
horses.cpp:10:21: note: shadowed declaration is here
10 | set<pair<int, int>> pos;
| ^~~
horses.cpp:102:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
102 | if (x[pos] == val) return compute();
| ~~~~~~~^~
horses.cpp:107:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
107 | return compute();
| ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:110:23: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
110 | signed updateY(signed pos, signed val) {
| ~~~~~~~^~~
horses.cpp:10:21: note: shadowed declaration is here
10 | set<pair<int, int>> pos;
| ^~~
horses.cpp:114:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
114 | return compute();
| ~~~~~~~^~
| # |
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 |
312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
971 ms |
64528 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 |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
