#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
ll n;
vi x;
vi y;
ll mod = 1e9+7;
class OldNode{
public:
ll val = 1;
ll dn,up;
OldNode *left;
OldNode *right;
OldNode(ll _dn,ll _up,vi &init){
dn = _dn;
up = _up;
if(dn+1!=up){
left = new OldNode(dn,(dn+up)/2,init);
right = new OldNode((dn+up)/2,up,init);
val = (left->val*right->val)%mod;
} else {
val = init[dn];
}
}
ll update(ll a,ll v){
if(dn>a||up<=a) return val;
if(dn+1==up) {
return val = v;
}
return val = (left->update(a,v)*right->update(a,v))%mod;
}
ll query(ll a,ll b){
if(dn>=b||up<=a) return 1;
if(a<=dn&&up<=b) return val;
return (left->query(a,b)*right->query(a,b))%mod;
}
};
pair<double,ll> op1(pair<double,ll> a,double b){
return {a.first+b,a.second};
}
class Node{
public:
pair<double,ll> val = {0,0};
double toPush = 0;
ll dn,up;
Node *left;
Node *right;
Node(ll _dn,ll _up,vector<double> &init){
dn = _dn;
up = _up;
if(dn+1!=up){
left = new Node(dn,(dn+up)/2,init);
right = new Node((dn+up)/2,up,init);
val = max(left->val,right->val);
} else {
val.second = dn;
val.first = init[dn];
}
}
void push(){
if(dn+1==up) return;
left->val=op1(left->val,toPush);
right->val=op1(right->val,toPush);
left->toPush+=toPush;
right->toPush+=toPush;
toPush = 0;
}
pair<double,ll> update(ll a,ll b,double v){
if(dn>=b||up<=a) return val;
if(a<=dn&&up<=b) {
val=op1(val,v);
toPush+=v;
return val;
}
push();
return val = max(left->update(a,b,v),right->update(a,b,v));
}
pair<double,ll> query(ll a,ll b){
if(dn>=b||up<=a) return {-1e18,0};
if(a<=dn&&up<=b) return val;
push();
return max(left->query(a,b),right->query(a,b));
}
};
Node *st;
OldNode *stMul;
ll getAns(){
ll index = st->query(0,n).second;
ll ans = (stMul->query(0,index+1)*y[index])%mod;
//cout<<ans<<endl;
return ans;
}
int init(int N, int X[], int Y[]) {
n = N;
x.resize(n,1);
y.resize(n,1);
rep(i,0,n) x[i] = X[i];
rep(i,0,n) y[i] = Y[i];
vector<double> stD(n);
stD[0] = log(x[0]);
rep(i,1,n) stD[i] = log(x[i]) + stD[i-1];
rep(i,0,n) stD[i] += log(y[i]);
st = new Node(0,N,stD);
stMul = new OldNode(0,N,x);
rep(i,0,n){
//updateX(i,X[i]);
//updateY(i,Y[i]);
}
/*cout<<"#######"<<endl;
rep(i,0,n) cout<<x[i]<<" ";
cout<<endl;
rep(i,0,n) cout<<y[i]<<" ";
cout<<endl;
rep(i,0,n) cout<<stMul->query(i,i+1)<<" ";
cout<<endl;
rep(i,0,n) cout<<st->query(i,i+1).first<<" ";
cout<<endl;
cout<<"#######"<<endl;*/
return getAns();
}
int updateX(int pos, int val) {
st->update(pos,n,-log(double(x[pos]))+log(double(val)));
stMul->update(pos,val);
x[pos] = val;
return getAns();
}
int updateY(int pos, int val) {
st->update(pos,pos+1,-log(y[pos])+log(val));
y[pos] = val;
return getAns();
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:149:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return getAns();
~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:156:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return getAns();
~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:162:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return getAns();
~~~~~~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
3 ms |
536 KB |
Output is correct |
4 |
Correct |
2 ms |
536 KB |
Output is correct |
5 |
Correct |
3 ms |
536 KB |
Output is correct |
6 |
Correct |
3 ms |
536 KB |
Output is correct |
7 |
Correct |
2 ms |
536 KB |
Output is correct |
8 |
Correct |
2 ms |
536 KB |
Output is correct |
9 |
Correct |
9 ms |
536 KB |
Output is correct |
10 |
Correct |
3 ms |
548 KB |
Output is correct |
11 |
Correct |
2 ms |
548 KB |
Output is correct |
12 |
Correct |
3 ms |
548 KB |
Output is correct |
13 |
Correct |
3 ms |
548 KB |
Output is correct |
14 |
Correct |
2 ms |
548 KB |
Output is correct |
15 |
Correct |
4 ms |
548 KB |
Output is correct |
16 |
Correct |
3 ms |
548 KB |
Output is correct |
17 |
Correct |
3 ms |
548 KB |
Output is correct |
18 |
Correct |
2 ms |
548 KB |
Output is correct |
19 |
Correct |
3 ms |
548 KB |
Output is correct |
20 |
Correct |
3 ms |
548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
548 KB |
Output is correct |
2 |
Correct |
3 ms |
548 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
4 ms |
600 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
600 KB |
Output is correct |
8 |
Correct |
2 ms |
600 KB |
Output is correct |
9 |
Correct |
2 ms |
600 KB |
Output is correct |
10 |
Correct |
2 ms |
600 KB |
Output is correct |
11 |
Correct |
3 ms |
600 KB |
Output is correct |
12 |
Correct |
3 ms |
600 KB |
Output is correct |
13 |
Correct |
2 ms |
600 KB |
Output is correct |
14 |
Correct |
2 ms |
600 KB |
Output is correct |
15 |
Correct |
3 ms |
600 KB |
Output is correct |
16 |
Correct |
2 ms |
600 KB |
Output is correct |
17 |
Correct |
3 ms |
600 KB |
Output is correct |
18 |
Correct |
3 ms |
600 KB |
Output is correct |
19 |
Correct |
2 ms |
600 KB |
Output is correct |
20 |
Correct |
3 ms |
600 KB |
Output is correct |
21 |
Correct |
3 ms |
600 KB |
Output is correct |
22 |
Correct |
3 ms |
600 KB |
Output is correct |
23 |
Correct |
5 ms |
748 KB |
Output is correct |
24 |
Correct |
5 ms |
876 KB |
Output is correct |
25 |
Correct |
5 ms |
876 KB |
Output is correct |
26 |
Correct |
5 ms |
940 KB |
Output is correct |
27 |
Correct |
4 ms |
940 KB |
Output is correct |
28 |
Correct |
4 ms |
940 KB |
Output is correct |
29 |
Correct |
4 ms |
940 KB |
Output is correct |
30 |
Correct |
5 ms |
940 KB |
Output is correct |
31 |
Correct |
4 ms |
940 KB |
Output is correct |
32 |
Correct |
5 ms |
940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
326 ms |
125924 KB |
Output is correct |
2 |
Correct |
654 ms |
125924 KB |
Output is correct |
3 |
Correct |
632 ms |
125944 KB |
Output is correct |
4 |
Correct |
773 ms |
125996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
125996 KB |
Output is correct |
2 |
Correct |
2 ms |
125996 KB |
Output is correct |
3 |
Correct |
3 ms |
125996 KB |
Output is correct |
4 |
Correct |
3 ms |
125996 KB |
Output is correct |
5 |
Correct |
4 ms |
125996 KB |
Output is correct |
6 |
Correct |
2 ms |
125996 KB |
Output is correct |
7 |
Correct |
0 ms |
125996 KB |
Output is correct |
8 |
Correct |
2 ms |
125996 KB |
Output is correct |
9 |
Correct |
2 ms |
125996 KB |
Output is correct |
10 |
Correct |
3 ms |
125996 KB |
Output is correct |
11 |
Correct |
3 ms |
125996 KB |
Output is correct |
12 |
Correct |
2 ms |
125996 KB |
Output is correct |
13 |
Correct |
2 ms |
125996 KB |
Output is correct |
14 |
Correct |
3 ms |
125996 KB |
Output is correct |
15 |
Correct |
2 ms |
125996 KB |
Output is correct |
16 |
Correct |
3 ms |
125996 KB |
Output is correct |
17 |
Correct |
3 ms |
125996 KB |
Output is correct |
18 |
Correct |
2 ms |
125996 KB |
Output is correct |
19 |
Correct |
3 ms |
125996 KB |
Output is correct |
20 |
Correct |
3 ms |
125996 KB |
Output is correct |
21 |
Correct |
2 ms |
125996 KB |
Output is correct |
22 |
Correct |
3 ms |
125996 KB |
Output is correct |
23 |
Correct |
4 ms |
125996 KB |
Output is correct |
24 |
Correct |
4 ms |
125996 KB |
Output is correct |
25 |
Correct |
4 ms |
125996 KB |
Output is correct |
26 |
Correct |
4 ms |
125996 KB |
Output is correct |
27 |
Correct |
4 ms |
125996 KB |
Output is correct |
28 |
Correct |
5 ms |
125996 KB |
Output is correct |
29 |
Correct |
4 ms |
125996 KB |
Output is correct |
30 |
Correct |
4 ms |
125996 KB |
Output is correct |
31 |
Correct |
4 ms |
125996 KB |
Output is correct |
32 |
Correct |
5 ms |
125996 KB |
Output is correct |
33 |
Correct |
289 ms |
125996 KB |
Output is correct |
34 |
Correct |
251 ms |
126040 KB |
Output is correct |
35 |
Correct |
301 ms |
126040 KB |
Output is correct |
36 |
Correct |
295 ms |
126040 KB |
Output is correct |
37 |
Correct |
235 ms |
126040 KB |
Output is correct |
38 |
Correct |
229 ms |
126040 KB |
Output is correct |
39 |
Correct |
210 ms |
126040 KB |
Output is correct |
40 |
Correct |
257 ms |
131772 KB |
Output is correct |
41 |
Correct |
229 ms |
134032 KB |
Output is correct |
42 |
Correct |
215 ms |
136084 KB |
Output is correct |
43 |
Correct |
249 ms |
142424 KB |
Output is correct |
44 |
Incorrect |
245 ms |
148824 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
148824 KB |
Output is correct |
2 |
Correct |
3 ms |
148824 KB |
Output is correct |
3 |
Correct |
3 ms |
148824 KB |
Output is correct |
4 |
Correct |
3 ms |
148824 KB |
Output is correct |
5 |
Correct |
4 ms |
148824 KB |
Output is correct |
6 |
Correct |
3 ms |
148824 KB |
Output is correct |
7 |
Correct |
3 ms |
148824 KB |
Output is correct |
8 |
Correct |
2 ms |
148824 KB |
Output is correct |
9 |
Correct |
2 ms |
148824 KB |
Output is correct |
10 |
Correct |
2 ms |
148824 KB |
Output is correct |
11 |
Correct |
2 ms |
148824 KB |
Output is correct |
12 |
Correct |
3 ms |
148824 KB |
Output is correct |
13 |
Correct |
2 ms |
148824 KB |
Output is correct |
14 |
Correct |
3 ms |
148824 KB |
Output is correct |
15 |
Correct |
3 ms |
148824 KB |
Output is correct |
16 |
Correct |
3 ms |
148824 KB |
Output is correct |
17 |
Correct |
3 ms |
148824 KB |
Output is correct |
18 |
Correct |
4 ms |
148824 KB |
Output is correct |
19 |
Correct |
2 ms |
148824 KB |
Output is correct |
20 |
Correct |
2 ms |
148824 KB |
Output is correct |
21 |
Correct |
3 ms |
148824 KB |
Output is correct |
22 |
Correct |
3 ms |
148824 KB |
Output is correct |
23 |
Correct |
4 ms |
148824 KB |
Output is correct |
24 |
Correct |
4 ms |
148824 KB |
Output is correct |
25 |
Correct |
4 ms |
148824 KB |
Output is correct |
26 |
Correct |
4 ms |
148824 KB |
Output is correct |
27 |
Correct |
5 ms |
148824 KB |
Output is correct |
28 |
Correct |
6 ms |
148824 KB |
Output is correct |
29 |
Correct |
3 ms |
148824 KB |
Output is correct |
30 |
Correct |
5 ms |
148824 KB |
Output is correct |
31 |
Correct |
4 ms |
148824 KB |
Output is correct |
32 |
Correct |
4 ms |
148824 KB |
Output is correct |
33 |
Correct |
310 ms |
148852 KB |
Output is correct |
34 |
Correct |
607 ms |
148888 KB |
Output is correct |
35 |
Correct |
602 ms |
148888 KB |
Output is correct |
36 |
Correct |
670 ms |
148924 KB |
Output is correct |
37 |
Correct |
281 ms |
148924 KB |
Output is correct |
38 |
Correct |
268 ms |
148924 KB |
Output is correct |
39 |
Correct |
275 ms |
148924 KB |
Output is correct |
40 |
Correct |
280 ms |
148924 KB |
Output is correct |
41 |
Correct |
215 ms |
148924 KB |
Output is correct |
42 |
Correct |
238 ms |
148924 KB |
Output is correct |
43 |
Correct |
224 ms |
148924 KB |
Output is correct |
44 |
Correct |
248 ms |
154792 KB |
Output is correct |
45 |
Correct |
248 ms |
156772 KB |
Output is correct |
46 |
Correct |
198 ms |
158768 KB |
Output is correct |
47 |
Correct |
255 ms |
165244 KB |
Output is correct |
48 |
Incorrect |
231 ms |
171644 KB |
Output isn't correct |
49 |
Halted |
0 ms |
0 KB |
- |