Submission #238885

#	Time	Username	Problem	Language	Result	Execution time	Memory
238885		nicolaalexandra	Horses (IOI15_horses)	C++14	17 / 100	100 ms	79736 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
#define DIM 500010
#define MOD 1000000009
using namespace std;

int n,m,i,tip,poz,val;
int x[DIM],y[DIM],X[DIM],Y[DIM],prod[DIM];
double sum_log[DIM];

int lg_put (int a, int b){
    if (!b)
        return 1;
    int nr = lg_put (a,b/2);
    if (b&1)
        return 1LL * nr * nr % MOD * 1LL * a % MOD;
    else return 1LL * nr * nr % MOD;
}

struct segment_tree{
    double maxi_log,lazy_log; /// logaritmii
    int maxi,lazy; /// produsele modulo
} aint[DIM*4];

void build (int nod, int st, int dr){
    if (st == dr){
        /// x[1] * x[2] * ... x[st] * y[st];
        aint[nod].maxi_log = sum_log[st] + log(y[st]);
        aint[nod].maxi = 1LL * prod[st] * y[st] % MOD;

        aint[nod].lazy = 1;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);


    if (aint[nod<<1].maxi_log > aint[(nod<<1)|1].maxi_log)
        aint[nod] = aint[nod<<1];
    else aint[nod] = aint[(nod<<1)|1];

    aint[nod].lazy = 1;
}


int init (int n, int X[], int Y[]){
    for (i=0;i<n;i++)
        x[i+1] = X[i], y[i+1] = Y[i];

    prod[0] = 1;
    for (i=1;i<=n;i++){
        sum_log[i] = sum_log[i-1] + log (x[i]);
        prod[i] = 1LL * prod[i-1] * x[i] % MOD;
    }

    build (1,1,n);

    return aint[1].maxi;
}

void update_lazy (int nod, int st, int dr){
    if (st != dr){
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
        aint[fiu_st].maxi_log += aint[nod].lazy_log;
        aint[fiu_st].lazy_log += aint[nod].lazy_log;
        aint[fiu_st].maxi = 1LL * aint[fiu_st].maxi * aint[nod].lazy % MOD;
        aint[fiu_st].lazy = 1LL * aint[fiu_st].lazy * aint[nod].lazy % MOD;

        aint[fiu_dr].maxi_log += aint[nod].lazy_log;
        aint[fiu_dr].lazy_log += aint[nod].lazy_log;
        aint[fiu_dr].maxi = 1LL * aint[fiu_dr].maxi * aint[nod].lazy % MOD;
        aint[fiu_dr].lazy = 1LL * aint[fiu_dr].lazy * aint[nod].lazy % MOD;
    }
    aint[nod].lazy_log = 0;
    aint[nod].lazy = 1;
}

void update (int nod, int st, int dr, int x, int y, double val_log, int val){
    update_lazy(nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].maxi_log += val_log;
        aint[nod].maxi = 1LL * aint[nod].maxi * val % MOD;

        aint[nod].lazy_log += val_log;
        aint[nod].lazy = 1LL * aint[nod].lazy * val % MOD;
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val_log,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val_log,val);
    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    if (aint[nod<<1].maxi_log > aint[(nod<<1)|1].maxi_log){
        aint[nod] = aint[nod<<1];
    } else aint[nod] = aint[(nod<<1)|1];

}


int updateX(int pos, int val) {

    pos++;

    update (1,1,n,pos,n,-log(x[pos]),lg_put(x[pos],MOD-2));

    x[pos] = val;

    update (1,1,n,pos,n,log(x[pos]),x[pos]);

    update_lazy (1,1,n);

	return aint[1].maxi;
}

int updateY(int pos, int val) {

	pos++;

	update (1,1,n,pos,pos,-log(y[pos]),lg_put(y[pos],MOD-2));
	y[pos] = val;

	update (1,1,n,pos,pos,log(y[pos]),y[pos]);

	update_lazy (1,1,n);

	return aint[1].maxi;
}

Compilation message (stderr)

horses.cpp: In function 'int lg_put(int, int)':
horses.cpp:16:46: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         return 1LL * nr * nr % MOD * 1LL * a % MOD;
                                              ^
horses.cpp:17:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     else return 1LL * nr * nr % MOD;
                               ^
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:29:49: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].maxi = 1LL * prod[st] * y[st] % MOD;
                                                 ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:47:34: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
 int init (int n, int X[], int Y[]){
                                  ^
horses.cpp:8:26: note: shadowed declaration is here
 int x[DIM],y[DIM],X[DIM],Y[DIM],prod[DIM];
                          ^
horses.cpp:47:34: warning: declaration of 'X' shadows a global declaration [-Wshadow]
 int init (int n, int X[], int Y[]){
                                  ^
horses.cpp:8:19: note: shadowed declaration is here
 int x[DIM],y[DIM],X[DIM],Y[DIM],prod[DIM];
                   ^
horses.cpp:47:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 int init (int n, int X[], int Y[]){
                                  ^
horses.cpp:7:5: note: shadowed declaration is here
 int n,m,i,tip,poz,val;
     ^
horses.cpp:54:42: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         prod[i] = 1LL * prod[i-1] * x[i] % MOD;
                                          ^
horses.cpp: In function 'void update_lazy(int, int, int)':
horses.cpp:67:70: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[fiu_st].maxi = 1LL * aint[fiu_st].maxi * aint[nod].lazy % MOD;
                                                                      ^
horses.cpp:68:70: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[fiu_st].lazy = 1LL * aint[fiu_st].lazy * aint[nod].lazy % MOD;
                                                                      ^
horses.cpp:72:70: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[fiu_dr].maxi = 1LL * aint[fiu_dr].maxi * aint[nod].lazy % MOD;
                                                                      ^
horses.cpp:73:70: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[fiu_dr].lazy = 1LL * aint[fiu_dr].lazy * aint[nod].lazy % MOD;
                                                                      ^
horses.cpp: In function 'void update(int, int, int, int, int, double, int)':
horses.cpp:79:76: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 void update (int nod, int st, int dr, int x, int y, double val_log, int val){
                                                                            ^
horses.cpp:7:19: note: shadowed declaration is here
 int n,m,i,tip,poz,val;
                   ^~~
horses.cpp:79:76: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 void update (int nod, int st, int dr, int x, int y, double val_log, int val){
                                                                            ^
horses.cpp:8:12: note: shadowed declaration is here
 int x[DIM],y[DIM],X[DIM],Y[DIM],prod[DIM];
            ^
horses.cpp:79:76: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void update (int nod, int st, int dr, int x, int y, double val_log, int val){
                                                                            ^
horses.cpp:8:5: note: shadowed declaration is here
 int x[DIM],y[DIM],X[DIM],Y[DIM],prod[DIM];
     ^
horses.cpp:83:53: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].maxi = 1LL * aint[nod].maxi * val % MOD;
                                                     ^
horses.cpp:86:53: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].lazy = 1LL * aint[nod].lazy * val % MOD;
                                                     ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:104:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateX(int pos, int val) {
                             ^
horses.cpp:7:19: note: shadowed declaration is here
 int n,m,i,tip,poz,val;
                   ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:119:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateY(int pos, int val) {
                             ^
horses.cpp:7:19: note: shadowed declaration is here
 int n,m,i,tip,poz,val;
                   ^~~

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