Submission #234552

#	Time	Username	Problem	Language	Result	Execution time	Memory
234552		triple_fault	Horses (IOI15_horses)	C++14	100 / 100	831 ms	72824 KiB

horses

#include "horses.h"
#include <vector>
#include <algorithm>
#include <cstdio>

#define MAX 500000
#define ll long long

#define lft 2 * v
#define rht (2 * v) + 1

ll MOD = 1e9 + 7;
using namespace std;

ll n;
ll y[MAX];
ll x[MAX];

vector<ll> seg_prod(MAX * 4);
vector<ll> seg_prod_max(MAX * 4);
vector<ll> seg_y(MAX * 4); 

void build(ll v, ll tl, ll tr) {
    if (tl == tr) {
        seg_prod[v] = x[tl];
        seg_prod_max[v] = x[tl];
    } else {
        ll mid = (tl + tr) / 2;
        build(lft, tl, mid);
        build(rht, mid + 1, tr);

        seg_prod[v] = (seg_prod[lft] * seg_prod[rht]) % MOD;
        seg_prod_max[v] = min(seg_prod_max[lft] * seg_prod_max[rht], MOD);
    }
}

void update(ll v, ll idx, ll tl, ll tr) {
    if (tl > tr) return;
    if (tl == idx && tl == tr) {
        seg_prod[v] = x[idx];
        seg_prod_max[v] = x[idx];
        return;
    }
    ll mid = (tl + tr) / 2;
    if (idx > mid) update(rht, idx, mid + 1, tr);
    else update(lft, idx, tl, mid);

    seg_prod[v] = (seg_prod[lft] * seg_prod[rht]) % MOD;
    seg_prod_max[v] = min(seg_prod_max[lft] * seg_prod_max[rht], MOD);
}

ll query1(ll v, ll l, ll r, ll tl, ll tr) {
    if (l > r) return 1;
    if (tl == l && tr == r) return seg_prod[v];

    ll mid = (tl + tr) / 2;
    ll ret = query1(lft, l, min(r, mid), tl, mid) *
        query1(rht, max(l, mid + 1), r, mid + 1, tr);
    return ret % MOD;
}

ll query2(ll v, ll l, ll r, ll tl, ll tr) {
    if (l > r) return 1;
    if (tl == l && tr == r) return seg_prod_max[v]; 

    ll mid = (tl + tr) / 2;
    ll ret = query2(lft, l, min(r, mid), tl, mid) *
        query2(rht, max(l, mid + 1), r, mid + 1, tr);
    return min(MOD, ret);
}

void build_y(ll v, ll tl, ll tr) {
    if (tl == tr) seg_y[v] = tl;
    else {
        ll mid = (tl + tr) / 2;
        build_y(lft, tl, mid);
        build_y(rht, mid + 1, tr);

        ll left = seg_y[lft];
        ll right = seg_y[rht];

        ll p1 = y[left]; ll p2 = query2(1, left + 1, right, 0, n - 1) * y[right];
        if (p2 > p1) seg_y[v] = right;
        else seg_y[v] = left;
    }
}

void update_y(ll v, ll idx, ll tl, ll tr) {
    if (tl > tr) return;
    if (tl == tr && tl == idx) {
        seg_y[v] = idx;
        return;
    }
    ll mid = (tl + tr) / 2;
    if (idx > mid) update_y(rht, idx, mid + 1, tr);
    else update_y(lft, idx, tl, mid);
    ll left = seg_y[lft];
    ll right = seg_y[rht];

    ll p1 = y[left]; ll p2 = query2(1, left + 1, right, 0, n - 1) * y[right];
    if (p2 > p1) seg_y[v] = right;
    else seg_y[v] = left;
}

ll find() {
    return (query1(1, 0, seg_y[1], 0, n - 1) * y[seg_y[1]]) % MOD;
}

int init(int N, int X[], int Y[]) {
    n = (ll)N;
    for (ll i = 0; i < n; ++i) y[i] = (ll)Y[i];
    for (ll i = 0; i < n; ++i) x[i] = (ll)X[i];

    build(1, 0, n - 1);
    build_y(1, 0, n - 1);
	return find();
}

int updateX(int pos, int val) {	
    x[pos] = val;
    update(1, pos, 0, n - 1);
    update_y(1, pos, 0, n - 1);
    return find();
}

int updateY(int pos, int val) {
    y[pos] = val;
    update_y(1, pos, 0, n - 1);
    return find();
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:116:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return find();
         ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return find();
            ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:129:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return find();
            ~~~~^~

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