#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<pair<int,double>> stl;
vector<double> lazy;
vector<ll> stm;
vector<int> x, y;
void updatem(int pos, int val, int node=1, int tl=0, int tr=n-1){
if (tl == tr){
stm[node] = val;
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) updatem(pos, val, node*2, tl, tm);
else updatem(pos, val, node*2+1, tm+1, tr);
stm[node] = (stm[node*2]*stm[node*2+1]) % 1000000007;
}
int querym(int l, int r, int node=1, int tl=0, int tr=n-1){
//cout << l << " " << r << " " << tl << " " << tr << "\n";
if (l <= tl && tr <= r) return stm[node];
int tm = (tl+tr)/2;
int res = 1;
if (l <= tm) res = (res*querym(l, r, node*2, tl, tm)) % 1000000007;
if (tm+1 <= r) res = (res*querym(l, r, node*2+1, tm+1, tr)) % 1000000007;
return res;
}
void prop(int node, int tl, int tr){
stl[node].second += lazy[node];
if (tl != tr){
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
pair<int,double> merge(int a, int b){
if (stl[a].second > stl[b].second) return stl[a];
return stl[b];
}
void updatel(int l, int r, double val, int node=1, int tl=0, int tr=n-1){
if (l <= tl && tr <= r){
lazy[node] += val;
prop(node, tl, tr);
return;
}
prop(node, tl, tr);
int tm = (tl+tr)/2;
if (l <= tm) updatel(l, r, val, node*2, tl, tm);
if (tm+1 <= r) updatel(l, r, val, node*2+1, tm+1, tr);
stl[node] = merge(node*2, node*2+1);
}
void updatelp(int pos, double val, int node=1, int tl=0, int tr=n-1){
prop(node, tl, tr);
if (tl == tr){
stl[node].first = pos;
stl[node].second += val;
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) updatelp(pos, val, node*2, tl, tm);
else updatelp(pos, val, node*2+1, tm+1, tr);
stl[node] = merge(node*2, node*2+1);
}
int init(int N, int X[], int Y[]){
n = N;
stl.resize(4*N, {-1, 0});
lazy.resize(4*N, 0);
stm.resize(4*N, 1);
x.resize(N);
y.resize(N);
for (int i=0; i<N; i++){
y[i] = Y[i];
x[i] = X[i];
updatem(i, X[i]);
updatelp(i, Y[i]);
updatel(i, N-1, log(X[i]));
}
/*for (int i=1; i<4*N; i++){
cout << stl[i].first << " " << stl[i].second << " | ";
if ((i+1) == pow(2, floor(log2(i+1)))) cout << "\n";
}*/
return querym(0, stl[1].first)*y[stl[1].first] % 1000000007;
}
int updateX(int pos, int val){
updatel(pos, n-1, log(val)-log(x[pos]));
x[pos] = val;
return querym(0, stl[1].first)*y[stl[1].first] % 1000000007;
}
int updateY(int pos, int val){
updatelp(pos, val-y[pos]);
y[pos] = val;
return querym(0, stl[1].first)*y[stl[1].first] % 1000000007;
}
Compilation message
horses.cpp: In function 'int querym(int, int, int, int, int)':
horses.cpp:26:41: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
26 | if (l <= tl && tr <= r) return stm[node];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
340 ms |
75860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
