제출 #310490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310490		amunduzbaev	말 (IOI15_horses)	C++14	0 / 100	1593 ms	122948 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=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:ans);
}

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

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

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

    push(lx,rx,pos);

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

void updY(int pos,int lx,int rx,node val,int nod){
    if(rx-lx==1){
        ans[nod]=val;
        return;
    }int mid=(lx+rx)/2;
    push(lx,rx,nod);
    if(mid > pos){
        updY(pos,lx,mid,val,nod*2);
    }else{
        updY(pos,mid,rx,val,nod*2+1);
    }
    ans[nod]=mx(ans[nod*2],ans[nod*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);
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'node mx(node, node)':
horses.cpp:21:22: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   21 | node mx(node a,node b){
      |                      ^
horses.cpp:10:9: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |         ^
horses.cpp:21:22: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   21 | 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:45:20: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   45 | ll binpow(ll a,ll b){
      |                    ^
horses.cpp:10:9: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |         ^
horses.cpp:45:20: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   45 | ll binpow(ll a,ll b){
      |                    ^
horses.cpp:10:4: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |    ^
horses.cpp:48:8: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
   48 |     ll ans=binpow(a,b/2)%MOD;
      |        ^~~
horses.cpp:17:14: note: shadowed declaration is here
   17 | vector<node> ans;
      |              ^~~
horses.cpp: In function 'node comb(node, node)':
horses.cpp:52:24: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   52 | node comb(node a,node b){ return {a.summ+b.summ,(a.answ*b.answ)%MOD};
      |                        ^
horses.cpp:10:9: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |         ^
horses.cpp:52:24: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   52 | node comb(node a,node b){ return {a.summ+b.summ,(a.answ*b.answ)%MOD};
      |                        ^
horses.cpp:10:4: note: shadowed declaration is here
   10 | ll a[N],b[N];
      |    ^
horses.cpp: In function 'void updX(int, int, int, int, node, int)':
horses.cpp:74:14: warning: left operand of comma operator has no effect [-Wunused-value]
   74 |     int mid=(lx,rx)/2;
      |              ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:102:33: warning: declaration of 's' shadows a global declaration [-Wshadow]
  102 | int init(int s, int x[], int y[]) {
      |                                 ^
horses.cpp:11:7: note: shadowed declaration is here
   11 | int n,s;
      |       ^
horses.cpp:109:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |     int ans1=ans[1].answ;
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:119:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |     return ans[1].answ;
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:1: warning: no return statement in function returning non-void [-Wreturn-type]
  128 | }
      | ^

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