Submission #552861

#	Time	Username	Problem	Language	Result	Execution time	Memory
552861		elazarkoren	Horses (IOI15_horses)	C++17	37 / 100	513 ms	53568 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;
const int infinity = 1e9;

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;
    }
};

struct SegMax {
    int n;
    vi seg;
    SegMax () {}
    SegMax (int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n);
    }
    void update(int i, int x) {
        seg[i += n] = x;
        for (i >>= 1; i; i >>= 1) {
            seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
        }
    }
    ll query(int l, int r) {
        ll ans = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) chkmax(ans, seg[l++]);
            if (r & 1) chkmax(ans, seg[--r]);
        }
        return ans;
    }
};

int n;
ll x[MAX_N], y[MAX_N];
set<int, greater<int>> changed;

Seg seg;
SegMax seg_max;

pii Comp(pii p1, pii p2) {
    if (p1.x > p2.x) swap(p1, p2);
    auto [v, moded] = seg.query(p1.x + 1, p2.x + 1);
    if (moded) return p2;
    ll y1 = seg_max.query(p1.x, p1.y), y2 = seg_max.query(p2.x, p2.y);
    return (y1 < v * y2 ? p2 : p1);
}

int Solve() {
    pii best = {0, 1};
    int cnt = 30;
    int last = n;
    changed.insert(0);
    for (int i : changed) {
        if (!(cnt--)) break;
        best = Comp({i, last}, best);
        last = i;
    }
    ll x1 = seg.query(0, best.x + 1).x;
    ll y1 = seg_max.query(best.x, best.y);
    return x1 * y1 % mod;
}

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

int updateX(int pos, int val) {
    if (x[pos] != 1) changed.erase(changed.find(pos));
    x[pos] = val;
    if (x[pos] != 1) changed.insert(pos);
    seg.update(pos, val);
    return Solve();
}

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

//3
//2 1 3
//3 4 1
//1
//2 1 2

Compilation message (stderr)

horses.cpp: In function 'int Solve()':
horses.cpp:117:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |     return x1 * y1 % mod;
      |            ~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:127:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  127 |         seg_max.update(i, y[i]);
      |                              ^

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