Submission #310270

#	Time	Username	Problem	Language	Result	Execution time	Memory
310270		juggernaut	Horses (IOI15_horses)	C++14	17 / 100	1589 ms	45932 KiB

horses

#include"horses.h"
#include<bits/stdc++.h>
//#include"grader.cpp"
using namespace std;
typedef long long ll;
ll mod=1e9+7;
struct node{
    ll ans,cur,need;
    double lg;
}tree[2000000];
ll n,res=1,x[500005],y[500005];
double loga=0;
void build(ll v,ll l,ll r){
    if(l==r){
        res=(res*x[l])%mod;
        loga+=log2(x[l]);
        tree[v].ans=(res*y[l])%mod;
        tree[v].lg=loga+log2(y[l]);
        tree[v].cur=(x[l]*y[l])%mod;
        tree[v].need=(x[l]*y[l])%mod;
        return;
    }
    ll mid=(l+r)>>1;
    build(v<<1,l,mid);
    build((v<<1)+1,mid+1,r);
    if(tree[v<<1].lg>tree[(v<<1)+1].lg)tree[v]=tree[v<<1];
    else tree[v]=tree[(v<<1)+1];
}
ll pw(ll a,ll b){
    if(!b)return 1ll;
    if(b&1)return (a*pw(a,b-1))%mod;
    ll x=pw(a,b>>1);
    return (x*x)%mod;
}
void push(int v,int l,int r){
    if(l!=r){
        tree[v<<1].cur=tree[v<<1].need;
        tree[v<<1].need=tree[v<<1].need;
        tree[(v<<1)+1].cur=tree[(v<<1)+1].need;
        tree[(v<<1)+1].need=tree[(v<<1)+1].need;
    }
    tree[v].lg-=log2(tree[v].cur);
    tree[v].lg+=log2(tree[v].need);
    tree[v].ans=(tree[v].ans*pw(tree[v].cur,mod-2))%mod;
    tree[v].ans=(tree[v].ans*tree[v].need)%mod;
    tree[v].cur=tree[v].need;
}
void update(ll v,ll l,ll r,ll ql,ll qr,ll val){
    push(v,l,r);
    if(qr<l||r<ql)return;
    if(ql<=l&&r<=qr){
        tree[v].cur=tree[v].need;
        tree[v].need=val;
        push(v,l,r);
        return;
    }
    ll mid=(l+r)>>1;
    update(v<<1,l,mid,ql,qr,val);
    update((v<<1)+1,mid+1,r,ql,qr,val);
    if(tree[v<<1].lg>tree[(v<<1)+1].lg)tree[v]=tree[v<<1];
    else tree[v]=tree[(v<<1)+1];
}
int init(int N,int X[],int Y[]){
	n=N;
	copy(X,X+n,x);
	copy(Y,Y+n,y);
	build(1,0,n-1);
	push(1,0,n-1);
	return tree[1].ans;
}
int updateX(int pos,int val){
	update(1,0,n-1,pos,n-1,val*y[pos]);
	x[pos]=val;
	push(1,0,n-1);
	return tree[1].ans;
}
int updateY(int pos,int val){
	update(1,0,n-1,pos,pos,val*x[pos]);
	y[pos]=val;
	push(1,0,n-1);
	return tree[1].ans;
}

Compilation message (stderr)

horses.cpp: In function 'll pw(ll, ll)':
horses.cpp:32:8: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   32 |     ll x=pw(a,b>>1);
      |        ^
horses.cpp:11:12: note: shadowed declaration is here
   11 | ll n,res=1,x[500005],y[500005];
      |            ^
horses.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
horses.cpp:49:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   49 |     push(v,l,r);
      |          ^
horses.cpp:49:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   49 |     push(v,l,r);
      |            ^
horses.cpp:49:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   49 |     push(v,l,r);
      |              ^
horses.cpp:54:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   54 |         push(v,l,r);
      |              ^
horses.cpp:54:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   54 |         push(v,l,r);
      |                ^
horses.cpp:54:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   54 |         push(v,l,r);
      |                  ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:68:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |  push(1,0,n-1);
      |           ~^~
horses.cpp:69:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |  return tree[1].ans;
      |         ~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:74:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   74 |  push(1,0,n-1);
      |           ~^~
horses.cpp:75:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   75 |  return tree[1].ans;
      |         ~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:80:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   80 |  push(1,0,n-1);
      |           ~^~
horses.cpp:81:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   81 |  return tree[1].ans;
      |         ~~~~~~~~^~~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23