Submission #310496

#	Time	Username	Problem	Language	Result	Execution time	Memory
310496		amunduzbaev	말 (IOI15_horses)	C++14	17 / 100	214 ms	78128 KiB

horses

//#include "grader.cpp"
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double

const int N=1e6+5;
const int MOD=1e9+7;
ll a[N],b[N];
int n,s;
struct node{
    ld summ;
    ll answ;
};
vector<node> ans;
vector<node> v;
node z={0. , 1ll};

node mx(node a,node b){
    if(a.summ>b.summ) return a;
    else return b;
}

void build(){
    s=1;
    while(s<n) s*=2;

    v.assign(s*2,z);
    ans.assign(s*2,z);

    for(int i=0;i<s;i++){
        v[i+s].answ=a[i];
        v[i+s].summ=log10(a[i]);
    }
    for(int i=1;i<s;i++){
        v[i+s].summ+=v[s+i-1].summ;
        v[i+s].answ*=v[s+i-1].answ;
        v[i+s].answ%=MOD;
    }
    for(int i=0;i<s;i++){
        ans[i+s].answ = (v[i+s].answ*b[i]) % MOD ;
        ans[i+s].summ = v[i+s].summ+log10(b[i]);
    }
    for(int i=s-1;i>0;i--)
        ans[i]=mx(ans[i*2+1],ans[i*2]);
}

ll binpow(ll a,ll b){
    if(b==0) return 1ll;
    if(b==1) return a;
    ll ans=binpow(a,b/2)%MOD;
    return (b%2==1 ? (ans*a)%MOD:ans);
}

node comb(node a,node b){
    return {a.summ+b.summ,(a.answ*b.answ)%MOD};
}
void push(int l,int r,int x){
    if(r==l+1) return;
    v[x*2]=comb(v[x],v[x*2]);
    v[x*2+1]=comb(v[x],v[x*2+1]);

    ans[x*2]=comb(ans[x],ans[x*2]);
    ans[x*2+1]=comb(ans[x],ans[x*2+1]);
    v[x]=z;
    ans[x]=mx(ans[x*2],ans[x*2+1]);
}

void updX(int l,int r,int lx,int rx,node val,int x){
    if(l>=rx||r<=lx) return;

    push(lx,rx,x);

    if(lx>=l&&rx<=r){
        v[x]=comb(v[x],val);
        ans[x]=comb(ans[x],val);
    }
    int mid=(lx+rx)/2;
    updX(l,r,lx,mid,val,x*2);
    updX(l,r,mid,rx,val,x*2+1);
    ans[x]=mx(ans[x*2],ans[x*2+1]);
}

void updY(int pos,int lx,int rx,node val,int x){
    if(rx-lx==1){
        ans[x]=val;
        return;
    }int mid=(lx+rx)/2;
    push(lx,rx,x);
    if(mid > pos){
        updY(pos,lx,mid,val,x*2);
    }else{
        updY(pos,mid,rx,val,x*2+1);
    }
    ans[x]=mx(ans[x*2],ans[x*2+1]);
}
node pref(int i){
    node ans1={0. ,1};
    for(i+=s;i>0;i/=2){
        ans1.summ+=v[i].summ;
        ans1.answ*=v[i].answ;
        ans1.answ%=MOD;
    }
    return ans1;
}
int init(int s, int x[], int y[]) {
    n=s;
    for(int i=0;i<n;i++){
        a[i]=x[i];
        b[i]=y[i];
    }
    build();
    int ans1=ans[1].answ;
    return ans1;
}

int updateX(int pos, int val) {
    a[pos]=val;
    int lx=0, rx=s, l=pos, r=s;
    node nod={(log10(val)-log10(a[pos])), (val*binpow(a[pos],MOD-2))%MOD};

    updX(lx,rx,l,r,nod,1);
    return ans[1].answ;
}

int updateY(int pos, int val) {
    b[pos]=val;

    node x=pref(pos);
    node nod={x.summ+log10(val),(x.answ*val)%MOD};
    updY(pos,0,s,nod,1);
    return ans[1].answ;
}

Compilation message (stderr)

horses.cpp: In function 'node mx(node, node)':
horses.cpp:20:22: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   20 | node mx(node a,node b){
      |                      ^
horses.cpp:10:9: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |         ^
horses.cpp:20:22: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   20 | node mx(node a,node b){
      |                      ^
horses.cpp:10:4: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |    ^
horses.cpp: In function 'long long int binpow(long long int, long long int)':
horses.cpp:49:20: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   49 | ll binpow(ll a,ll b){
      |                    ^
horses.cpp:10:9: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |         ^
horses.cpp:49:20: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   49 | ll binpow(ll a,ll b){
      |                    ^
horses.cpp:10:4: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |    ^
horses.cpp:52:8: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
   52 |     ll ans=binpow(a,b/2)%MOD;
      |        ^~~
horses.cpp:16:14: note: shadowed declaration is here
   16 | vector<node> ans;
      |              ^~~
horses.cpp: In function 'node comb(node, node)':
horses.cpp:56:24: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   56 | node comb(node a,node b){
      |                        ^
horses.cpp:10:9: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |         ^
horses.cpp:56:24: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   56 | node comb(node a,node b){
      |                        ^
horses.cpp:10:4: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:107:33: warning: declaration of 's' shadows a global declaration [-Wshadow]
  107 | int init(int s, int x[], int y[]) {
      |                                 ^
horses.cpp:11:7: note: shadowed declaration is here
   11 | int n,s;
      |       ^
horses.cpp:114:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |     int ans1=ans[1].answ;
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:124:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  124 |     return ans[1].answ;
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:133:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |     return ans[1].answ;

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