Submission #98915

#	Time	Username	Problem	Language	Result	Execution time	Memory
98915		psmao	Horses (IOI15_horses)	C++14	100 / 100	252 ms	46352 KiB

horses

//每个马在每一个地方都一个价值 找最大的一个地方
// ∏x[i](i->j) * y[j] 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+12;
const int mod=1e9+7;
int n,x[maxn],y[maxn];


struct Tree
{
    int mx,num;
    double val,sum;
}tree[maxn<<2];


void pushup(int now)
{
    if(tree[now<<1].val>tree[now<<1].sum+tree[now<<1|1].val) 
    {
        tree[now].val=tree[now<<1].val;
        tree[now].mx=tree[now<<1].mx;
    }
    else 
    {
        tree[now].val=tree[now<<1].sum+tree[now<<1|1].val;
        tree[now].mx=1LL*tree[now<<1].num*tree[now<<1|1].mx%mod;
    }
    tree[now].num=1LL*tree[now<<1].num*tree[now<<1|1].num%mod;
    tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
}

void build(int l,int r,int now)
{
    if(l==r) 
    {
        tree[now].mx=1LL*x[l]*y[l]%mod;
        tree[now].num=x[l];
        tree[now].val=log(1.0*x[l]*y[l]);
        tree[now].sum=log(1.0*x[l]);
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,now<<1);build(mid+1,r,now<<1|1);
    pushup(now);
}

void updata(int L,int l,int r,int now)
{
    if(l==r) 
    {
        tree[now].mx=1LL*x[l]*y[l]%mod;
        tree[now].num=x[l];
        tree[now].val=log(1.0*x[l]*y[l]);
        tree[now].sum=log(1.0*x[l]);//log相加就是相乘 
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid) updata(L,l,mid,now<<1);
    else updata(L,mid+1,r,now<<1|1);
    pushup(now);
}

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];
    build(1,n,1);
    return tree[1].mx;
}

int updateX(int pos, int val) 
{
    x[pos+1]=val;updata(pos+1,1,n,1);
    return tree[1].mx;
}

int updateY(int pos, int val) 
{
    y[pos+1]=val;updata(pos+1,1,n,1);
    return tree[1].mx;
}

Compilation message (stderr)

horses.cpp: In function 'void pushup(int)':
horses.cpp:28:60: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         tree[now].mx=1LL*tree[now<<1].num*tree[now<<1|1].mx%mod;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:30:58: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     tree[now].num=1LL*tree[now<<1].num*tree[now<<1|1].num%mod;
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:38:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         tree[now].mx=1LL*x[l]*y[l]%mod;
                      ~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void updata(int, int, int, int)':
horses.cpp:53:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         tree[now].mx=1LL*x[l]*y[l]%mod;
                      ~~~~~~~~~~~~~^~~~

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