#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const ll MOD = 1e9 + 7;
ll X[MAXN], Y[MAXN];
inline ll mult(ll a, ll b) {return (a * b) % MOD;}
ll exp(ll x, ll b)
{
if (b == 0) return 1LL;
if (b % 2) return mult(x, exp(x, b-1));
else return exp(mult(x, x), b/2);
}
int N;
struct node
{
ll mx, y;
bool bigPref;
ll val;
node (ll MX = 0, ll Y = 0, bool BIG = false) : mx(MX), y(Y), bigPref(BIG) {val = mult(mx, y);}
node operator+(node outro)
{
node resp;
/*
Quero ver se outro.mx * outro.y >= y, mas pode dar overflow, ent
testo tres casos:
se outro.y >= y, ja eh maior
se o outro tem um prefixo grande(tive que tirar mod), tbm eh maior
//Agr, tenho certeza que mx <= 1e9 e y <= 1e9, ent posso testar a multiplicao
se (outro.mx * outro.y) >= y, eh maior
senao o maior sera o proprio y.
*/
if (y <= outro.y) resp = node(mult(mx, outro.mx), outro.y, ((mx * outro.mx >= MOD) || bigPref || outro.bigPref));
else if (outro.bigPref) resp = node(mult(mx, outro.mx), outro.y, true);
else if ((outro.mx * outro.y) >= y) resp = node(mult(mx, outro.mx), outro.y, ((mx * outro.mx >= MOD) || bigPref || outro.bigPref));
else resp = *this;
return resp;
}
} seg[4*MAXN];
void build(int pos, int ini, int fim)
{
if (ini == fim)
{
seg[pos] = node(X[ini], Y[ini]);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
build(e, ini, m );
build(d, m+1, fim);
seg[pos] = seg[e] + seg[d];
}
void segUpdate(int pos, int ini, int fim, int id)
{
if (id < ini || id > fim) return;
if (ini == fim)
{
seg[pos] = node(X[ini], Y[ini]);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
segUpdate(e, ini, m , id);
segUpdate(d, m+1, fim, id);
seg[pos] = seg[e] + seg[d];
}
int init(int _N, int _X[], int _Y[])
{
N = _N;
for (int i = 1; i <= N; i++) X[i] = _X[i-1], Y[i] = _Y[i-1];
build(1, 1, N);
return seg[1].val;
}
int updateX(int id, int _val)
{
++id;
X[id] = _val;
segUpdate(1, 1, N, id);
return seg[1].val;
}
int updateY(int id, int _val)
{
++id;
Y[id] = _val;
segUpdate(1, 1, N, id);
return seg[1].val;
}
Compilation message
horses.cpp: In constructor 'node::node(ll, ll, bool)':
horses.cpp:24:22: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
24 | node (ll MX = 0, ll Y = 0, bool BIG = false) : mx(MX), y(Y), bigPref(BIG) {val = mult(mx, y);}
| ~~~^~~~~
horses.cpp:7:13: note: shadowed declaration is here
7 | ll X[MAXN], Y[MAXN];
| ^
horses.cpp: In constructor 'node::node(ll, ll, bool)':
horses.cpp:24:22: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
24 | node (ll MX = 0, ll Y = 0, bool BIG = false) : mx(MX), y(Y), bigPref(BIG) {val = mult(mx, y);}
| ~~~^~~~~
horses.cpp:7:13: note: shadowed declaration is here
7 | ll X[MAXN], Y[MAXN];
| ^
horses.cpp: In constructor 'node::node(ll, ll, bool)':
horses.cpp:24:22: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
24 | node (ll MX = 0, ll Y = 0, bool BIG = false) : mx(MX), y(Y), bigPref(BIG) {val = mult(mx, y);}
| ~~~^~~~~
horses.cpp:7:13: note: shadowed declaration is here
7 | ll X[MAXN], Y[MAXN];
| ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:82:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
82 | return seg[1].val;
| ~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:90:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
90 | return seg[1].val;
| ~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:98:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
98 | return seg[1].val;
| ~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
62884 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
62920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
62880 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
62832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
79388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
62932 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
62936 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
62932 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
62932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
