Submission #117717

#	Time	Username	Problem	Language	Result	Execution time	Memory
117717		zubec	Horses (IOI15_horses)	C++14	17 / 100	271 ms	58744 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;


const ll MOD = 1e9+7;
const int N = 500100;
const ll MAX = 2000000000;

int n;

int tmx[N*4], a[N], b[N];

struct node{
    ll val, ans;
    ld sum, mx;
};

node combine(node lft, node rgt){
    node res;
    if (lft.mx < lft.sum+rgt.mx){
        res.mx = lft.sum+rgt.mx;
        res.ans = (lft.val*rgt.ans)%MOD;
    } else {
        res.mx = lft.mx;
        res.ans = lft.ans;
    }
    res.val = (lft.val*rgt.val)%MOD;
    res.sum = (lft.sum+rgt.sum);
    return res;
}

node t[N*4];

void build(int v, int l, int r){
    if (l == r){
        t[v].val = a[l];
        t[v].sum = log((ld)a[l]);
        t[v].mx = log((ld)a[l])+log((ld)b[l]);
        t[v].ans = a[l]*b[l]%MOD;
        return;
    }
    int mid = (l+r)>>1;
    build(v+v, l, mid);
    build(v+v+1, mid+1, r);
    t[v] = combine(t[v+v], t[v+v+1]);
}

void update(int v, int l, int r, int pos){
    if (l == r){
        t[v].val = a[l];
        t[v].sum = log((ld)a[l]);
        t[v].mx = log((ld)a[l])+log((ld)b[l]);
        t[v].ans = a[l]*b[l]%MOD;
        return;
    }
    int mid = (l+r)>>1;
    if (pos <= mid)
        update(v+v, l, mid, pos); else
        update(v+v+1, mid+1, r, pos);
    t[v] = combine(t[v+v], t[v+v+1]);
}

int query(){
    return t[1].ans;
}

int init(int N, int X[], int Y[]) {
    n = N;
    for (int i = 1; i <= n; i++){
        a[i] = X[i-1];
        b[i] = Y[i-1];
    }
    build(1, 1, n);
    return query();
}

int updateX(int pos, int val) {
    ++pos;
    a[pos] = val;
    update(1, 1, n, pos);
    return query();
}

int updateY(int pos, int val) {
    ++pos;
    b[pos] = val;
    update(1, 1, n, pos);
    return query();
}

/**

3
2 1 3
3 4 1
1
2 1 2



*/

Compilation message (stderr)

horses.cpp: In function 'int query()':
horses.cpp:67:17: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return t[1].ans;
            ~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:70:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:9:11: note: shadowed declaration is here
 const int N = 500100;
           ^

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