Submission #387178

#	Time	Username	Problem	Language	Result	Execution time	Memory
387178		ParsaAlizadeh	Horses (IOI15_horses)	C++17	100 / 100	290 ms	73456 KiB

horses

#include  <bits/stdc++.h>
#include "horses.h"
using namespace std;

#define lc (id << 1)
#define rc (lc | 1)

typedef long long ll;

struct Node {
    int ind;
    ll v1 = 1, v2 = 1;
};

int const MOD = 1e9 + 7;

int n;
vector<int> A, B;
vector<Node> mxseg;
vector<ll> valseg;

inline ll mul(ll x, ll y) {
    return x * y > MOD ? 0 : x * y;
}

Node mxmerge(Node const& l, Node const& r) {
    Node res;
    ll val = mul(l.v2, mul(r.v1, B[r.ind]));
    if (val == 0 || val >= B[l.ind]) {
        res.ind = r.ind;
        res.v1 = mul(l.v1, mul(l.v2, r.v1));
        res.v2 = r.v2;
    }
    else {
        res.ind = l.ind;
        res.v1 = l.v1;
        res.v2 = mul(l.v2, mul(r.v1, r.v2));
    }
    return res;
}

void mxbuild(int id, int l, int r, int ind) {
    if (ind != -1 && (ind < l || r <= ind))
        return;
    if (r - l == 1) {
        mxseg[id].ind = l;
        mxseg[id].v1 = A[l];
        return;
    }
    int mid = (l + r) >> 1;
    mxbuild(lc, l, mid, ind);
    mxbuild(rc, mid, r, ind);
    mxseg[id] = mxmerge(mxseg[lc], mxseg[rc]);
}

void valbuild(int id, int l, int r, int ind) {
    if (ind != -1 && (ind < l || r <= ind))
        return;
    if (r - l == 1) {
        valseg[id] = A[l];
        return;
    }
    int mid = (l + r) >> 1;
    valbuild(lc, l, mid, ind);
    valbuild(rc, mid, r, ind);
    valseg[id] = valseg[lc] * valseg[rc] % MOD;
}

ll valget(int id, int l, int r, int qr) {
    if (r <= qr)
        return valseg[id];
    if (qr <= l)
        return 1;
    int mid = (l + r) >> 1;
    return valget(lc, l, mid, qr) * valget(rc, mid, r, qr) % MOD;
}

int query() {
    int ind = mxseg[1].ind;
    return valget(1, 0, n, ind + 1) * B[ind] % MOD;
}

int init(int N, int X[], int Y[]) {
    n = N;
    A.assign(X, X + n);
    B.assign(Y, Y + n);
    mxseg.resize((n + 1) << 2);
    valseg.resize((n + 1) << 2);
    mxbuild(1, 0, n, -1);
    valbuild(1, 0, n, -1);
    return query();
}

int updateX(int pos, int val) {
    A[pos] = val;
    mxbuild(1, 0, n, pos);
    valbuild(1, 0, n, pos);
    return query();
}

int updateY(int pos, int val) {
    B[pos] = val;
    mxbuild(1, 0, n, pos);
    valbuild(1, 0, n, pos);
    return query();
}

Compilation message (stderr)

horses.cpp: In function 'int query()':
horses.cpp:80:46: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   80 |     return valget(1, 0, n, ind + 1) * B[ind] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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