Submission #134250

#	Time	Username	Problem	Language	Result	Execution time	Memory
134250		Runtime_error_	말 (IOI15_horses)	C++14	100 / 100	1468 ms	131484 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define le node+node
#define ri node+node+1
#define mid (l+r)/2
using namespace std;
const ll inf = 5e5+9,mod = 1e9+7;
ll n,dp2[inf],x[inf],y[inf];
ld dp1[inf];

ll power(ll x,ll n,ll M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return power((x*x)%M,n/2,M);
    else
        return (x*power((x*x)%M,(n-1)/2,M))%M;

}

struct Node{

    ld mx1 , lzy1;
    ll mx2 , lzy2;

    Node(ll idx = 0){
        lzy1 = 0.0;
        lzy2 = 1;
        mx1 = dp1[idx];
        mx2 = dp2[idx];
    }
};
Node tree[inf<<2];

Node merge(Node x , Node y){
    if(x.mx1 >= y.mx1)
        return x;
    return y;
}

void push(int node,int l,int r){

    if(tree[node].lzy2 == 1)
        return ;
    tree[node].mx1 += tree[node].lzy1;
    tree[node].mx2 = (tree[node].mx2 * tree[node].lzy2)%mod;
    if(l!=r)
        tree[le].lzy1 += tree[node].lzy1, tree[le].lzy2 = (tree[le].lzy2 * tree[node].lzy2)%mod,
        tree[ri].lzy1 += tree[node].lzy1, tree[ri].lzy2 = (tree[ri].lzy2 * tree[node].lzy2)%mod;
    tree[node].lzy2 = 1,tree[node].lzy1 = 0.0;
}

void build(int node,int l,int r){

    if(l == r)
        return void(tree[node] = Node(l));

    build(le,l,mid);
    build(ri,mid+1,r);
    tree[node] = merge( tree[le] , tree[ri] );
}

void update(int node,int l,int r,int x,int y,ll val,int sign){

    push(node,l,r);
    if(l>r || r<x || l>y)
        return ;
    if(l>=x && r<=y){
        if(sign == -1){
            tree[node].lzy1 = -1.0*log(1.0*val);
            tree[node].lzy2 = power(val,mod-2,mod);
        }
        else{
            tree[node].lzy1 = 1.0*log(1.0*val);
            tree[node].lzy2 = val;
        }
        push(node,l,r);
        return;
    }
    update(le,l,mid,x,y,val,sign);
    update(ri,mid+1,r,x,y,val,sign);
    tree[node] = merge( tree[le] , tree[ri] );
}


void calc(){

    ld lcur=log(1.0),lret = 0.0,ltmp=0.0;

	ll cur = 1,ret = 0,tmp=0;

	for(int i=1;i<=n;i++){
        cur = (cur*x[i])%mod;
        lcur += log(1.0*x[i]);

        tmp = (cur*y[i])%mod;
        ltmp = lcur+log(1.0*y[i]);

        if(ltmp>=lret)
            lret = ltmp,ret = tmp;

        dp1[i] = ltmp;
        dp2[i] = tmp;
	}

}

int init(int N, int X[], int Y[]) {

    n = N;
    for(int i=1;i<=N;i++)
        x[i] = X[i-1] , y[i] = Y[i-1];
    calc();
    build(1,1,n);
    //cout<<tree[1].mx2<<endl;

    return tree[1].mx2;
}

int updateX(int pos, int val) {
    pos++;

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

    x[pos] = val;

    update(1,1,n,pos,n,x[pos],1);
    //cout<<tree[1].mx2<<endl;

    return tree[1].mx2;
}

int updateY(int pos, int val) {
    pos++;

    update(1,1,n,pos,pos,y[pos],-1);
    y[pos] = val;
    update(1,1,n,pos,pos,y[pos],1);
    //cout<<tree[1].mx2<<endl;
	return tree[1].mx2;
}

Compilation message (stderr)

horses.cpp: In function 'long long int power(long long int, long long int, long long int)':
horses.cpp:13:24: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ll power(ll x,ll n,ll M)
                        ^
horses.cpp:10:4: note: shadowed declaration is here
 ll n,dp2[inf],x[inf],y[inf];
    ^
horses.cpp:13:24: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 ll power(ll x,ll n,ll M)
                        ^
horses.cpp:10:15: note: shadowed declaration is here
 ll n,dp2[inf],x[inf],y[inf];
               ^
horses.cpp: In function 'Node merge(Node, Node)':
horses.cpp:38:27: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 Node merge(Node x , Node y){
                           ^
horses.cpp:10:22: note: shadowed declaration is here
 ll n,dp2[inf],x[inf],y[inf];
                      ^
horses.cpp:38:27: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 Node merge(Node x , Node y){
                           ^
horses.cpp:10:15: note: shadowed declaration is here
 ll n,dp2[inf],x[inf],y[inf];
               ^
horses.cpp: In function 'void update(int, int, int, int, int, long long int, int)':
horses.cpp:66:61: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 void update(int node,int l,int r,int x,int y,ll val,int sign){
                                                             ^
horses.cpp:10:22: note: shadowed declaration is here
 ll n,dp2[inf],x[inf],y[inf];
                      ^
horses.cpp:66:61: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void update(int node,int l,int r,int x,int y,ll val,int sign){
                                                             ^
horses.cpp:10:15: note: shadowed declaration is here
 ll n,dp2[inf],x[inf],y[inf];
               ^
horses.cpp:73:44: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
             tree[node].lzy1 = -1.0*log(1.0*val);
                                            ^~~
horses.cpp:77:43: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
             tree[node].lzy1 = 1.0*log(1.0*val);
                                           ^~~
horses.cpp: In function 'void calc()':
horses.cpp:97:28: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
         lcur += log(1.0*x[i]);
                         ~~~^
horses.cpp:100:32: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
         ltmp = lcur+log(1.0*y[i]);
                             ~~~^
horses.cpp:93:13: warning: variable 'ret' set but not used [-Wunused-but-set-variable]
  ll cur = 1,ret = 0,tmp=0;
             ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:117:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     build(1,1,n);
                ^
horses.cpp:120:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return tree[1].mx2;
            ~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:126:33: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     update(1,1,n,pos,n,x[pos],-1);
                                 ^
horses.cpp:126:33: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:130:32: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     update(1,1,n,pos,n,x[pos],1);
                                ^
horses.cpp:130:32: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:133:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return tree[1].mx2;
            ~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:139:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     update(1,1,n,pos,pos,y[pos],-1);
                                   ^
horses.cpp:141:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     update(1,1,n,pos,pos,y[pos],1);
                                  ^
horses.cpp:143:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return tree[1].mx2;
         ~~~~~~~~^~~

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