This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#include "horses.h"
#endif // LOCAL
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
#define pb push_back
#define mp make_pair
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
int Pow(int x , int y){
if(y == 0)return 1;
int r = Pow(x,y/2);
if(y & 1)return (ll)r * r % mod * x % mod;
return (ll)r * r % mod;
}
ld a[maxn];
int p[maxn];
struct node{
int s , lz;
ld mx , mlz;
}s[maxn * 4];
ii val[maxn];
int n;
void build(int x , int l , int r){
s[x].lz = 1;
if(l == r){
s[x].s = (ll)p[l] * val[l].second % mod;
s[x].mx = a[l] + log2(val[l].second);
return;
}
int mid = l + r >> 1;
build(x*2,l,mid);build(x*2+1,mid+1,r);
if(s[x * 2].mx > s[x * 2 + 1].mx){
s[x] = s[x * 2];
}else{
s[x] = s[x * 2 + 1];
}
}
void push(int x , bool key){
s[x].mx += s[x].mlz;
s[x].s = (ll)s[x].s * s[x].lz % mod;
if(key){
s[x * 2].mlz += s[x].mlz;
s[x * 2 + 1].mlz += s[x].mlz;
s[x * 2].lz = (ll)s[x * 2].lz * s[x].lz % mod;
s[x * 2 + 1].lz = (ll)s[x * 2 + 1].lz * s[x].lz % mod;
}
s[x].mlz = 0;s[x].lz = 1;
}
int L , R , bb;
ld aa;
void update(int x ,int l , int r){
push(x,l!=r);
if(l > R || L > r)return;
if(L <= l && r <= R){
s[x].mlz += aa;
s[x].lz = (ll)s[x].lz * bb % mod;
push(x,l!=r);
return;
}
int mid = l + r >> 1;
update(x*2,l,mid);
update(x*2+1,mid+1,r);
if(s[x * 2].mx > s[x * 2 + 1].mx){
s[x] = s[x * 2];
}else{
s[x] = s[x * 2 + 1];
}
}
int init(int N, int X[], int Y[]) {
p[0] = 1;
n = N;
for(int i = 1 ; i <= n ; ++i){
val[i] = mp(X[i - 1] , Y[i - 1]);
}
for(int i = 1 ; i <= n ; ++i){
a[i] = a[i - 1] + log2(val[i].first);
p[i] = (ll)p[i - 1] * val[i].first % mod;
}
build(1,1,n);
return s[1].s;
}
int updateX(int pos, int val) {
pos++;
ld a = -log2(::val[pos].first);
int b = Pow(::val[pos].first,mod-2);
::val[pos].first = val;
a += log2(::val[pos].first);
b = (ll)b * ::val[pos].first % mod;
L = pos;R = n;aa = a;bb = b;
update(1,1,n);
return s[1].s;
}
int updateY(int pos, int val) {
pos++;
ld a = -log2(::val[pos].second);
int b = Pow(::val[pos].second,mod-2);
::val[pos].second = val;
a += log2(::val[pos].second);
b = (ll)b * ::val[pos].second % mod;
L = pos;R = pos;aa = a;bb = b;
update(1,1,n);
return s[1].s;
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if(fopen("a.inp", "r")) {
freopen("a.inp", "r", stdin);
freopen("a.out", "w", stdout);
}
int N; cin >> N;
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) {
cin >> X[i];
}
for (int i = 0; i < N; i++) {
cin >> Y[i];
}
cout << init(N,X,Y) << endl;
int M;cin >> M;
for (int i = 0; i < M; i++) {
int pos , val , type;
cin >> type >> pos >> val;
if (type == 1) {
cout << updateX(pos,val) << endl;
} else if (type == 2) {
cout << updateY(pos,val) << endl;
}
}
return 0;
}
#endif // LOCAL
Compilation message (stderr)
horses.cpp: In function 'int Pow(int, int)':
horses.cpp:19:41: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
if(y & 1)return (ll)r * r % mod * x % mod;
~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:20:22: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return (ll)r * r % mod;
~~~~~~~~~~^~~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:35:43: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
s[x].s = (ll)p[l] * val[l].second % mod;
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
horses.cpp: In function 'void push(int, bool)':
horses.cpp:50:35: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
s[x].s = (ll)s[x].s * s[x].lz % mod;
~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:54:49: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
s[x * 2].lz = (ll)s[x * 2].lz * s[x].lz % mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:55:57: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
s[x * 2 + 1].lz = (ll)s[x * 2 + 1].lz * s[x].lz % mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void update(int, int, int)':
horses.cpp:67:36: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
s[x].lz = (ll)s[x].lz * bb % mod;
~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:88:44: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
p[i] = (ll)p[i - 1] * val[i].first % mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:94:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
int updateX(int pos, int val) {
^
horses.cpp:29:4: note: shadowed declaration is here
ii val[maxn];
^~~
horses.cpp:96:8: warning: declaration of 'a' shadows a global declaration [-Wshadow]
ld a = -log2(::val[pos].first);
^
horses.cpp:23:4: note: shadowed declaration is here
ld a[maxn];
^
horses.cpp:100:34: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
b = (ll)b * ::val[pos].first % mod;
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:106:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
int updateY(int pos, int val) {
^
horses.cpp:29:4: note: shadowed declaration is here
ii val[maxn];
^~~
horses.cpp:108:8: warning: declaration of 'a' shadows a global declaration [-Wshadow]
ld a = -log2(::val[pos].second);
^
horses.cpp:23:4: note: shadowed declaration is here
ld a[maxn];
^
horses.cpp:112:35: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
b = (ll)b * ::val[pos].second % mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |