Submission #332320

#	Time	Username	Problem	Language	Result	Execution time	Memory
332320		Azert	Horses (IOI15_horses)	C++14	100 / 100	1044 ms	25324 KiB

horses

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

const long long INF = 1e9 + 4;
const int MAX = 5e5 + 5;
const int MOD = 1e9 + 7;
int n;
int x[MAX], y[MAX];
int m[MAX * 4], mm[MAX * 4], st[MAX * 4];

void initMul(int idx, int l, int r) {
    if (l == r) {
        m[idx] = mm[idx] = x[l];
        return;
    }

    int mid = (l + r) / 2;
    initMul(idx * 2, l, mid);
    initMul(idx * 2 + 1, mid + 1, r);

    m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD;
    mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]);
}

int get(int idx, int l, int r, int posL, int posR, int type) {
    if (posR < l || posL > r) return 1;

    if (posL <= l && r <= posR) return type? m[idx] : mm[idx];

    int mid = (l + r) / 2;
    if (type) {
        return (1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type)) % MOD;
    }
    return min(INF, 1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type));
}

void initSt(int idx, int l, int r) {
    if (l == r) {
        st[idx] = l;
        return;
    }

    int mid = (l + r) / 2;
    initSt(idx * 2, l, mid);
    initSt(idx * 2 + 1, mid + 1, r);

    int ll = st[idx * 2];
    int rr = st[idx * 2 + 1];
    if (1LL * y[rr] * get(1, 0, n - 1, ll + 1, rr, 0) >= y[ll]) st[idx] = rr;
    else st[idx] = ll;
}

int get() {
    int pos = st[1];
    return (1LL * get(1, 0, n - 1, 0, pos, 1) * y[pos]) % MOD;
}

void updateM(int idx, int l, int r, int pos) {
    if (pos < l || pos > r) return;

    if (l == r) {
        m[idx] = mm[idx] = x[pos];
        return;
    }

    int mid = (l + r) / 2;
    updateM(idx * 2, l, mid, pos);
    updateM(idx * 2 + 1, mid + 1, r, pos);

    m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD;
    mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]);
}

void update(int idx, int l, int r, int pos) {
    if (pos > r || pos < l) return;
    if (l == r) return;

    int mid = (l + r) / 2;
    update(idx * 2, l, mid, pos);
    update(idx * 2 + 1, mid + 1, r, pos);

    int ll = st[idx * 2];
    int rr = st[idx * 2 + 1];
    if (1LL * y[rr] * get(1, 0, n - 1, ll + 1, rr, 0) >= y[ll]) st[idx] = rr;
    else st[idx] = ll;
}

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

    initMul(1, 0, n - 1);
    // exit(0);
    initSt(1, 0, n - 1);

    return get();
}

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

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

// // #ifdef ONLINE_JUDGE
// int main() {
//     int xx[2] = {1000000000, 1000000000};
//     int yy[3] = {1000000000, 1000000000};
//     cout << init(2, xx, yy) << "\n";
//     // cout << updateY(1, 2) << "\n";
// }
// #endif

Compilation message (stderr)

horses.cpp: In function 'void initMul(int, int, int)':
horses.cpp:21:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   21 |     m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:22:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |     mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]);
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get(int, int, int, int, int, int)':
horses.cpp:32:112: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   32 |         return (1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type)) % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:34:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |     return min(INF, 1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type));
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:55:57: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   55 |     return (1LL * get(1, 0, n - 1, 0, pos, 1) * y[pos]) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void updateM(int, int, int, int)':
horses.cpp:70:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |     m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:71:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |     mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]);
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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