#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define pdl pair<double,long long>
#define mod (long long)1000000007
int n;
long long a[maxn];
long long b[maxn];
pdl tree[maxn*4];
pdl lazy[maxn*4];
pdl fus(pdl x,pdl y) {
return {x.first+y.first,(x.second*y.second+mod)%mod};
}
long long inv(long long value){
if(value == 1) return 1;
long long tmp = (inv(mod%value)*((-mod)/value));
tmp %= mod;
if(tmp < 0) tmp += mod;
return tmp;
}
void upd(int now) {
tree[now] = fus(tree[now],lazy[now]);
lazy[now<<1] = fus(lazy[now<<1],lazy[now]);
lazy[now<<1|1] = fus(lazy[now<<1|1],lazy[now]);
lazy[now] = {0,1};
}
void update(int now,int l,int r,int x,int y,double val1,long long val2) {
upd(now);
if(l>r || l>y || r<x) return ;
if(x<=l && r<=y) {
lazy[now] = {val1,val2};
upd(now);
return ;
}
int mid = (l+r)/2;
update(now<<1,l,mid,x,y,val1,val2); update(now<<1|1,mid+1,r,x,y,val1,val2);
tree[now] = max(tree[now<<1],tree[now<<1|1]);
}
void build(int now,int l,int r) {
if(l==r) {
tree[now] = lazy[now] = {0,1};
return ;
}
int mid = (l+r)/2;
build(now<<1,l,mid); build(now<<1|1,mid+1,r);
tree[now] = lazy[now] = {0,1};
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i=0;i<n;i++) a[i] = X[i], b[i] = Y[i];
build(1,0,n-1);
for(int i=0;i<n;i++) update(1,0,n-1,i,n-1,(double)log2(a[i]),a[i]);
for(int i=0;i<n;i++) update(1,0,n-1,i,i,(double)log2(b[i]),b[i]);
upd(1);
return tree[1].second;
}
int updateX(int pos, int val) {
update(1,0,n-1,pos,n-1,-(double)log2(a[pos]),inv(a[pos]));
a[pos] = val;
update(1,0,n-1,pos,n-1,(double)log2(a[pos]),a[pos]);
upd(1);
return tree[1].second;
}
int updateY(int pos, int val) {
update(1,0,n-1,pos,pos,-(double)log2(b[pos]),inv(b[pos]));
b[pos] = val;
update(1,0,n-1,pos,pos,(double)log2(b[pos]),b[pos]);
upd(1);
return tree[1].second;
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:63:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return tree[1].second;
^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:71:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return tree[1].second;
^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:79:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return tree[1].second;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 2 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 3 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 4 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 5 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 6 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 7 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 8 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 9 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 10 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 11 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 12 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 13 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 14 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 15 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 16 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 17 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 18 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 19 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 20 |
Correct |
0 ms |
142664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 2 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 3 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 4 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 5 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 6 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 7 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 8 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 9 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 10 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 11 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 12 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 13 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 14 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 15 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 16 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 17 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 18 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 19 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 20 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 21 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 22 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 23 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 24 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 25 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 26 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 27 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 28 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 29 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 30 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 31 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 32 |
Correct |
0 ms |
142664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
906 ms |
146576 KB |
Output is correct |
| 2 |
Correct |
1029 ms |
146576 KB |
Output is correct |
| 3 |
Correct |
976 ms |
146576 KB |
Output is correct |
| 4 |
Correct |
1049 ms |
146576 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 2 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 3 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 4 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 5 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 6 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 7 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 8 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 9 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 10 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 11 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 12 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 13 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 14 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 15 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 16 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 17 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 18 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 19 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 20 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 21 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 22 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 23 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 24 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 25 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 26 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 27 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 28 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 29 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 30 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 31 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 32 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 33 |
Correct |
886 ms |
146576 KB |
Output is correct |
| 34 |
Correct |
816 ms |
146576 KB |
Output is correct |
| 35 |
Correct |
843 ms |
146576 KB |
Output is correct |
| 36 |
Correct |
803 ms |
146576 KB |
Output is correct |
| 37 |
Correct |
813 ms |
146576 KB |
Output is correct |
| 38 |
Correct |
766 ms |
146576 KB |
Output is correct |
| 39 |
Correct |
739 ms |
146576 KB |
Output is correct |
| 40 |
Correct |
789 ms |
146576 KB |
Output is correct |
| 41 |
Correct |
756 ms |
146576 KB |
Output is correct |
| 42 |
Correct |
766 ms |
146576 KB |
Output is correct |
| 43 |
Correct |
776 ms |
146576 KB |
Output is correct |
| 44 |
Correct |
793 ms |
146576 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 2 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 3 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 4 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 5 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 6 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 7 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 8 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 9 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 10 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 11 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 12 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 13 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 14 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 15 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 16 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 17 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 18 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 19 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 20 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 21 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 22 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 23 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 24 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 25 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 26 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 27 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 28 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 29 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 30 |
Correct |
0 ms |
142664 KB |
Output is correct |
| 31 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 32 |
Correct |
3 ms |
142664 KB |
Output is correct |
| 33 |
Correct |
966 ms |
146576 KB |
Output is correct |
| 34 |
Correct |
1086 ms |
146576 KB |
Output is correct |
| 35 |
Correct |
1039 ms |
146576 KB |
Output is correct |
| 36 |
Correct |
1026 ms |
146576 KB |
Output is correct |
| 37 |
Correct |
809 ms |
146576 KB |
Output is correct |
| 38 |
Correct |
779 ms |
146576 KB |
Output is correct |
| 39 |
Correct |
793 ms |
146576 KB |
Output is correct |
| 40 |
Correct |
776 ms |
146576 KB |
Output is correct |
| 41 |
Correct |
746 ms |
146576 KB |
Output is correct |
| 42 |
Correct |
783 ms |
146576 KB |
Output is correct |
| 43 |
Correct |
729 ms |
146576 KB |
Output is correct |
| 44 |
Correct |
796 ms |
146576 KB |
Output is correct |
| 45 |
Correct |
719 ms |
146576 KB |
Output is correct |
| 46 |
Correct |
696 ms |
146576 KB |
Output is correct |
| 47 |
Correct |
736 ms |
146576 KB |
Output is correct |
| 48 |
Correct |
833 ms |
146576 KB |
Output is correct |
| 49 |
Correct |
1109 ms |
146576 KB |
Output is correct |
| 50 |
Correct |
1153 ms |
146576 KB |
Output is correct |
| 51 |
Correct |
959 ms |
146576 KB |
Output is correct |
| 52 |
Correct |
933 ms |
146576 KB |
Output is correct |
| 53 |
Correct |
996 ms |
146576 KB |
Output is correct |
| 54 |
Correct |
986 ms |
146576 KB |
Output is correct |
| 55 |
Correct |
889 ms |
146576 KB |
Output is correct |
| 56 |
Correct |
1016 ms |
146576 KB |
Output is correct |
| 57 |
Correct |
929 ms |
146576 KB |
Output is correct |
| 58 |
Correct |
956 ms |
146576 KB |
Output is correct |
| 59 |
Correct |
809 ms |
146576 KB |
Output is correct |
