Submission #96482

#	Time	Username	Problem	Language	Result	Execution time	Memory
96482		figter001	Horses (IOI15_horses)	C++14	54 / 100	802 ms	58356 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 5e5+50;
const ll oo = 1e9+1;
const int mod = 1e9+7;

ll x[N],y[N],nn,seg[4*N],id[4*N];
double lx[N],ly[N],ls[4*N];
int l,r;

ll get(int n,int s,int e){
    if(s > r || e < l)return 1;
    if(s >= l && e <= r)return seg[n];
    return (get(n*2,s,(s+e)/2)*get(n*2+1,(s+e)/2+1,e))%mod;
}

double getL(int n,int s,int e){
    if(s > r || e < l)return 0;
    if(s >= l && e <= r)return ls[n];
    return getL(n*2,s,(s+e)/2)+getL(n*2+1,(s+e)/2+1,e);
}

void build(int n,int s,int e){
    if(s == e){
        seg[n] = x[s];
        ls[n] = lx[s];
        return;
    }
    build(n*2,s,(s+e)/2);
    build(n*2+1,(s+e)/2+1,e);
    seg[n] = (seg[n*2] * seg[n*2+1])%mod;
    ls[n] = ls[n*2]+ls[n*2+1];
}

void buildL(int n,int s,int e){
    if(s == e){
        id[n]=s;
        return;
    }
    buildL(n*2,s,(s+e)/2);
    buildL(n*2+1,(s+e)/2+1,e);
    l = 1;
    r = id[n*2];
    double v = getL(1,1,nn);
    double sum1 = ly[id[n*2]]+v;
    r = id[n*2+1];
    v = getL(1,1,nn);
    double sum2 = ly[id[n*2+1]]+v;
    if(sum1 >= sum2)id[n] = id[n*2];
    else id[n] = id[n*2+1];
}

void update(int n,int s,int e){
    if(s > r || e < l)return;
    if(s >= l && e <= r){
        seg[n] = x[s];
        ls[n] = lx[s];
        return;
    }
    update(n*2,s,(s+e)/2);
    update(n*2+1,(s+e)/2+1,e);
    seg[n] = (seg[n*2] * seg[n*2+1])%mod;
    ls[n] = ls[n*2]+ls[n*2+1];
}

void updateL(int n,int s,int e){
    if(s > r || e < l)return;
    if(s==e)return;
    updateL(n*2,s,(s+e)/2);
    updateL(n*2+1,(s+e)/2+1,e);
    l = 1;
    r = id[n*2];
    double v = getL(1,1,nn);
    double sum1 = ly[id[n*2]]+v;
    r = id[n*2+1];
    v = getL(1,1,nn);
    double sum2 = ly[id[n*2+1]]+v;
    if(sum1 >= sum2)id[n] = id[n*2];
    else id[n] = id[n*2+1];
}

ll solve(){
    l = 1;
    r = id[1];
  return (y[id[1]]*get(1,1,nn))%mod;
}

int init(int N, int X[], int Y[]) {
    for(int i=1;i<=N;i++){
        x[i] = X[i-1];
        y[i] = Y[i-1];
        lx[i] = log(x[i]);
        ly[i] = log(y[i]);
    }
    nn = N;
    build(1,1,nn);
    buildL(1,1,nn);
    return solve();
}

int updateX(int pos, int val) {
    pos++;
    x[pos] = val;
    lx[pos] = log(val);
    l = r = pos;
    update(1,1,nn);
    updateL(1,1,nn);
    return solve();
}

int updateY(int pos, int val) {
    pos++;
    y[pos] = val;
    ly[pos] = log(val);
    l=r=pos;
    updateL(1,1,nn); 
    return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void buildL(int, int, int)':
horses.cpp:48:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     r = id[n*2];
         ~~~~~~^
horses.cpp:49:27: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     double v = getL(1,1,nn);
                           ^
horses.cpp:51:17: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     r = id[n*2+1];
         ~~~~~~~~^
horses.cpp:52:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     v = getL(1,1,nn);
                    ^
horses.cpp: In function 'void updateL(int, int, int)':
horses.cpp:77:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     r = id[n*2];
         ~~~~~~^
horses.cpp:78:27: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     double v = getL(1,1,nn);
                           ^
horses.cpp:80:17: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     r = id[n*2+1];
         ~~~~~~~~^
horses.cpp:81:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     v = getL(1,1,nn);
                    ^
horses.cpp: In function 'll solve()':
horses.cpp:89:13: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     r = id[1];
         ~~~~^
horses.cpp:90:30: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return (y[id[1]]*get(1,1,nn))%mod;
                              ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:93:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:8:11: note: shadowed declaration is here
 const int N = 5e5+50;
           ^
horses.cpp:101:17: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     build(1,1,nn);
                 ^
horses.cpp:102:18: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     buildL(1,1,nn);
                  ^
horses.cpp:103:17: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return solve();
            ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:111:18: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     update(1,1,nn);
                  ^
horses.cpp:112:19: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     updateL(1,1,nn);
                   ^
horses.cpp:113:17: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return solve();
            ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:121:19: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     updateL(1,1,nn); 
                   ^
horses.cpp:122:17: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return solve();
            ~~~~~^~

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