Submission #552855

#	Time	Username	Problem	Language	Result	Execution time	Memory
552855		elazarkoren	Horses (IOI15_horses)	C++17	34 / 100	1561 ms	24288 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 5e5 + 5;
const int mod = 1e9 + 7;


struct Seg {
    int n;
    vi seg;
    vb moded;
    Seg () {}
    Seg (int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n, 1);
        moded.resize(2 * n);
    }
    void pull(int i) {
        seg[i] = seg[i << 1] * seg[i << 1 | 1];
        moded[i] = moded[i << 1] | moded[i << 1 | 1];
    }
    void update(int i, ll x) {
        seg[i += n] = x;
        for (i >>= 1; i; i >>= 1) {
            pull(i);
            if (seg[i] >= mod) {
                moded[i] = true;
                seg[i] %= mod;
            }
        }
    }
    pair<ll, bool> query(int l, int r) {
        pair<ll, bool> p = {1, false};
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                p.x *= seg[l];
                p.y |= moded[l];
                l++;
            }
            if (r & 1) {
                r--;
                p.x *= seg[r];
                p.y |= moded[r];
            }
            if (p.x >= mod) {
                p.y = true;
                p.x %= mod;
            }
        }
        return p;
    }
};

int n;
ll x[MAX_N], y[MAX_N];
Seg seg;

int Comp(int i, int j) {
    auto [v, moded] = seg.query(i + 1, j + 1);
    if (moded) return j;
    return (y[i] < v * y[j] ? j : i);
}

int Solve() {
    int best = 0;
    for (int i = 1; i < n; i++) {
        best = Comp(best, i);
    }
    return seg.query(0, best + 1).x * y[best] % mod;
}

int init(int N, int X[], int Y[]) {
    n = N;
    seg = Seg(n);
    for (int i = 0; i < n; i++) {
        x[i] = X[i], y[i] = Y[i];
        seg.update(i, x[i]);
    }
    return Solve();
}

int updateX(int pos, int val) {
    x[pos] = val;
    seg.update(pos, val);
    return Solve();
}

int updateY(int pos, int val) {
    y[pos] = val;
    return Solve();
}

Compilation message (stderr)

horses.cpp: In function 'int Solve()':
horses.cpp:81:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |     return seg.query(0, best + 1).x * y[best] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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