| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 96500 | SecretAgent007 | Horses (IOI15_horses) | C++17 | 0 ms | 0 KiB |
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 "horses.h"
#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define mod 1000000007
vector<int> x(500003);
vector<int> y(500003);
int n;
int power(int b, int e){
if(e == 0) return 1;
if(e%2 == 1){
int a = power(b, e/2);
return ((a*a)%mod*b)%mod;
}else{
int a = power(b,e/2);
return (a*a)%mod;
}
}
int divi(int a, int b){
return ((a%mod)*(power(b%mod,mod-2))%mod)%mod;
}
struct node{
node* l, *r;
double nbHorselog;
double coeflog;
int nbHorseMod;
int coefMod;
};
void Merge(node* &root){
if(root->l->nbHorselog >= (double)(0.69314718055994528623) && root->r->nbHorselog >= (double)(0.69314718055994528623)){
if(root->l->nbHorselog+root->r->nbHorselog+(root->r->coeflog) > root->l->nbHorselog+(root->l->coeflog)){
root->nbHorselog = root->l->nbHorselog+root->r->nbHorselog;
root->coeflog = (root->r->coeflog);
root->nbHorseMod = (root->l->nbHorseMod*root->r->nbHorseMod)%mod;
root->coefMod = root->r->coefMod;
return;
}else{
root->nbHorselog = root->l->nbHorselog+root->r->nbHorselog;
root->coeflog = (root->l->nbHorselog+(root->l->coeflog))-root->nbHorselog;
root->nbHorseMod = (root->l->nbHorseMod*root->r->nbHorseMod)%mod;
root->coefMod = divi(((root->l->coefMod)%mod), root->r->nbHorseMod);
return;
}
}
if(root->l->nbHorselog == 0){
if(root->l->coeflog <= root->r->nbHorselog+root->r->coeflog){
root->nbHorselog = root->r->nbHorselog;
root->coeflog = root->r->coeflog;
root->nbHorseMod = root->r->nbHorseMod;
root->coefMod = root->r->coefMod;
}else{
root->nbHorselog = root->r->nbHorselog;
root->coeflog = root->l->coeflog-root->nbHorselog;
root->nbHorseMod = root->r->nbHorseMod;
root->coefMod = divi(root->l->coefMod, root->nbHorseMod);
}
return;
}else if(root->r->nbHorselog == 0){
if(root->r->coeflog+root->l->nbHorselog >= root->l->nbHorselog+root->l->coeflog){
root->nbHorselog = root->l->nbHorselog;
root->coeflog = root->r->coeflog;
root->nbHorseMod = root->l->nbHorseMod;
root->coefMod = root->r->coefMod;
}else{
root->nbHorselog = root->l->nbHorselog;
root->coeflog = root->l->nbHorselog+root->l->coeflog-root->nbHorselog;
root->nbHorseMod = root->l->nbHorseMod;
root->coefMod = divi(((root->l->nbHorseMod*root->l->coefMod)%mod), root->nbHorseMod);
}
}
}
void Build(node* root, int l, int r){
if(l == r){
root->l = root->r = NULL;
root->nbHorselog = log((x[l]));
root->coeflog = log((y[l]));
root->coefMod = y[l]%mod;
root->nbHorseMod = x[l]%mod;
return;
}
node* le = new node{NULL};
node* ri = new node{NULL};
int mid = (l+r)/2;
root->l = le;
root->r = ri;
Build(root->l, l, mid);
Build(root->r, mid+1, r);
Merge(root);
}
void Query(int l, int r, int p, int v, node* root, int c){
if(l == p && r == p){
if(c == 1){
root->nbHorselog = log(v);
root->nbHorseMod = v%mod;
}else{
root->coeflog = log(v);
root->coefMod = v%mod;
}
return;
}
int mid = (l+r)/2;
if(l <= p && mid >=p)Query(l, mid, p,v,root->l, c);
if(mid+1 <= p && r >= p)Query(mid+1, r, p, v, root->r, c);
Merge(root);
}
node* root = new node{NULL,NULL,1,1};
int init(int N, int X[], int Y[]) {
for(int i = 0; i < n; i++)x[i+1] = x[i];
for(int i = 0; i < n; i++)y[i+1] = y[i];
Build(root,1,N);
return (root->nbHorseMod*root->coefMod)%mod;
}
int updateX(int pos, int val) {
Query(1,n,pos+1,val,root,1);
return (root->nbHorseMod*root->coefMod)%mod;
}
int updateY(int pos, int val) {
Query(1,n,pos+1,val,root,2);
return (root->nbHorseMod*root->coefMod)%mod;
}