Submission #612395

#	Time	Username	Problem	Language	Result	Execution time	Memory
612395		yuto1115	Horses (IOI15_horses)	C++17	100 / 100	327 ms	70944 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n)-1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int mod = 1000000007;

using S = pair<ll, ll>;

const S e = {1, 0};

constexpr S op(const S &a, const S &b) {
    return {a.first * b.first % mod, max(a.second, b.second)};
}

class segtree {
    int n;
    vector<S> d;
    
    void update(int p) {
        d[p] = op(d[2 * p], d[2 * p + 1]);
    }

public:
    segtree(const vector<S> &init = {}) {
        n = 1;
        while (n < SZ(init)) n *= 2;
        d.assign(2 * n, e);
        rep(i, SZ(init)) d[n + i] = init[i];
        rrep2(i, n, 1) update(i);
    }
    
    void set(int p, const S &x) {
        assert(0 <= p and p < n);
        p += n;
        d[p] = x;
        while (p > 1) {
            p >>= 1;
            update(p);
        }
    }
    
    S prod(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        S res = e;
        while (l < r) {
            if (l & 1) res = op(res, d[l++]);
            if (r & 1) res = op(res, d[--r]);
            l >>= 1, r >>= 1;
        }
        return res;
    }
};

int n;
vl x, y;

segtree st;
set<int> bd;

int calc() {
    auto it = prev(bd.end());
    vector<S> v;
    rep(_, 30) {
        if (it == bd.begin()) break;
        int r = *it, l = *(--it);
        v.pb(st.prod(l, r));
    }
    reverse(all(v));
//    for(auto [f,s] : v) cerr << f << ' ' << s << endl;
    int mx = 0;
    ll now = 1;
    rep2(i, 1, SZ(v)) {
        now *= v[i].first;
        chmin(now, (ll) inf);
        if (now * v[i].second > v[mx].second) {
            mx = i;
            now = 1;
        }
    }
//    cerr << mx << endl;
    ll res = st.prod(0, *it).first;
    rep(i, mx + 1) {
        res *= v[i].first;
        res %= mod;
    }
    res *= v[mx].second;
    res %= mod;
    return res;
}

int init(int N, int X[], int Y[]) {
    n = N;
    x = vl(X, X + N);
    y = vl(Y, Y + N);
    vector<S> init(n);
    rep(i, n) init[i] = {x[i], y[i]};
    st = segtree(init);
    bd.insert(0);
    bd.insert(n);
    rep2(i, 1, n) if (x[i] > 1) bd.insert(i);
    return calc();
}

int updateX(int pos, int val) {
    if (pos) {
        if (x[pos] > 1 and val == 1) bd.erase(pos);
        if (x[pos] == 1 and val > 1) bd.insert(pos);
    }
    x[pos] = val;
    st.set(pos, {x[pos], y[pos]});
    return calc();
}

int updateY(int pos, int val) {
    y[pos] = val;
    st.set(pos, {x[pos], y[pos]});
    return calc();
}

Compilation message (stderr)

horses.cpp: In constructor 'segtree::segtree(const std::vector<std::pair<long long int, long long int> >&)':
horses.cpp:68:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |         rrep2(i, n, 1) update(i);
      |                               ^
horses.cpp: In function 'int calc()':
horses.cpp:116:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |             mx = i;
      |                  ^
horses.cpp:128:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |     return res;
      |            ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:140:43: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
  140 |     rep2(i, 1, n) if (x[i] > 1) bd.insert(i);
      |                                           ^

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