제출 #238902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238902		nicolaalexandra	말 (IOI15_horses)	C++14	100 / 100	721 ms	70168 KiB

horses

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

using namespace std;

int x[DIM],y[DIM],XX[DIM],YY[DIM],prod[DIM];
long double sum_log[DIM];
int n;

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[]){
    n = N;
    for (int i=0;i<n;i++)
        x[i+1] = X[i], y[i+1] = Y[i];

    prod[0] = 1;
    for (int 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++;
  
    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;
}

컴파일 시 표준 에러 (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: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, long double, int)':
horses.cpp:79: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:8:12: note: shadowed declaration is here
 int x[DIM],y[DIM],XX[DIM],YY[DIM],prod[DIM];
            ^
horses.cpp:79: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:8:5: note: shadowed declaration is here
 int x[DIM],y[DIM],XX[DIM],YY[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;
                                                     ^

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