Submission #238901

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

horses

#include <bits/stdc++.h>
#include "horses.h"
#define DIM 500010
#define MOD 1000000007 /// puneam 10^9 + 9.............

using namespace std;

int n,m,i,tip,poz,val;
int x[DIM],y[DIM],XX[DIM],YY[DIM],prod[DIM];
long double sum_log[DIM];

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

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

void build (int nod, int st, int dr){
    aint[nod].lazy = 1;
    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;
        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];

}


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, long 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;

        update_lazy(nod,st,dr);
        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].maxi_log = aint[nod<<1].maxi_log;
        aint[nod].maxi = aint[nod<<1].maxi;
    } else {
        aint[nod].maxi_log = aint[(nod<<1)|1].maxi_log;
        aint[nod].maxi = aint[(nod<<1)|1].maxi;
    }
}


int updateX(int pos, int val) {

    pos++;

 //   cout<<-log(x[pos])<<" "<<lg_put(x[pos],MOD-2)<<"\n";

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

    x[pos] = val;

   // cout<<log(x[pos])<<" "<<x[pos]<<"\n";

    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++;

   // cout<<-log(y[pos])<<" "<<lg_put(y[pos],MOD-2)<<"\n";

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

    //cout<<log(y[pos])<<" "<<y[pos]<<"\n";
	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:17:46: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         return 1LL*(1LL * nr * nr % MOD) * a % MOD;
                                              ^
horses.cpp:18:32: 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:31: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:46:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 int init (int n, int X[], int Y[]){
                                  ^
horses.cpp:8:5: note: shadowed declaration is here
 int n,m,i,tip,poz,val;
     ^
horses.cpp:53: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:66: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:67: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:71: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:72: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, long double, int)':
horses.cpp:78:81: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 void update (int nod, int st, int dr, int x, int y, long double val_log, int val){
                                                                                 ^
horses.cpp:8:19: note: shadowed declaration is here
 int n,m,i,tip,poz,val;
                   ^~~
horses.cpp:78:81: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 void update (int nod, int st, int dr, int x, int y, long double val_log, int val){
                                                                                 ^
horses.cpp:9:12: note: shadowed declaration is here
 int x[DIM],y[DIM],XX[DIM],YY[DIM],prod[DIM];
            ^
horses.cpp:78:81: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void update (int nod, int st, int dr, int x, int y, long double val_log, int val){
                                                                                 ^
horses.cpp:9:5: note: shadowed declaration is here
 int x[DIM],y[DIM],XX[DIM],YY[DIM],prod[DIM];
     ^
horses.cpp:82: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:85: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:109:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateX(int pos, int val) {
                             ^
horses.cpp:8:19: note: shadowed declaration is here
 int n,m,i,tip,poz,val;
                   ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateY(int pos, int val) {
                             ^
horses.cpp:8: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