Submission #68614

#	Time	Username	Problem	Language	Result	Execution time	Memory
68614		MANcity	Horses (IOI15_horses)	C++14	34 / 100	29 ms	10268 KiB

horses

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "horses.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int n;
LL X[100002];
LL Y[100002];
struct vert
{
    double gum;
    double ans;
    int pos;
}t[4*100002];
void combine(int v)
{
    if(t[2*v].ans>=(t[2*v].gum+t[2*v+1].ans))
    {
        t[v].ans=t[2*v].ans;
        t[v].pos=t[2*v].pos;
    }
    else
    {
        t[v].ans=(t[2*v].gum+t[2*v+1].ans);
        t[v].pos=t[2*v+1].pos;
    }
    t[v].gum=(t[2*v].gum+t[2*v+1].gum);
}
void build(int left,int right,int v)
{
    if(left==right)
    {
        t[v].gum=(double)log(X[left]);
        t[v].ans=(double)log(X[left])+(double)log(Y[left]);
        t[v].pos=left;
    }
    else
    {
        int m=(left+right)/2;
        build(left,m,2*v);
        build(m+1,right,2*v+1);
        combine(v);
    }
}
void update(int left,int right,int pos,int v)
{
    if(left==right)
    {
        t[v].gum=(double)log(X[left]);
        t[v].ans=(double)log(X[left])+(double)log(Y[left]);
        t[v].pos=left;
    }
    else
    {
        int m=(left+right)/2;
        if(pos<=m)
            update(left,m,pos,2*v);
        else
            update(m+1,right,pos,2*v+1);
        combine(v);
    }
}
LL mult[4*100002];
void build2(int left,int right,int v)
{
    if(left==right)
        mult[v]=X[left];
    else
    {
        int m=(left+right)/2;
        build2(left,m,2*v);
        build2(m+1,right,2*v+1);
        mult[v]=((LL)mult[2*v]*(LL)mult[2*v+1])%Mod;
    }
}
LL get2(int left,int right,int l,int r,int v)
{
    if(l>r)
        return 1;
    if(left==l && right==r)
        return mult[v];
    int m=(left+right)/2;
    LL A=get2(left,m,l,min(r,m),2*v);
    LL B=get2(m+1,right,max(l,m+1),r,2*v+1);
    return ((LL)A*(LL)B)%Mod;
}
void update2(int left,int right,int pos,int v)
{
    if(left==right)
    {
        mult[v]=X[left];
    }
    else
    {
        int m=(left+right)/2;
        if(pos<=m)
            update2(left,m,pos,2*v);
        else
            update2(m+1,right,pos,2*v+1);
        mult[v]=((LL)mult[2*v]*(LL)mult[2*v+1])%Mod;
    }
}
int init(int n_0, int x_0[], int y_0[]) {
    n=n_0;
    for1(i,n)
        X[i]=x_0[i-1];
    for1(i,n)
        Y[i]=y_0[i-1];
    build(1,n,1);
    build2(1,n,1);
    return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
}

int updateX(int pos, int val) {
    X[pos+1]=val;
    update(1,n,pos+1,1);
    update2(1,n,pos+1,1);
    return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
}

int updateY(int pos, int val) {
    Y[pos+1]=val;
    update(1,n,pos+1,1);
    return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:129:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:136:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:142:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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