제출 #99194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99194		eriksuenderhauf	말 (IOI15_horses)	C++11	100 / 100	1424 ms	52888 KiB

horses

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "horses.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const ll INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
ll pr[MAXN], x[MAXN], y[MAXN], tree[MAXN * 2], BIT[MAXN];
int n = 0;

ll qry(int ind) {
    ll ret = 1;
    ind++;
    while (ind > 0) {
        ret = (BIT[ind] * ret) % MOD;
        ind -= ind & -ind;
    }
    return ret;
}

void upd(int ind, ll val) {
    ind++;
    while (ind <= n) {
        BIT[ind] = (BIT[ind] * val) % MOD;
        ind += ind & -ind;
    }
}

ll pw(ll a, ll b) {
    ll ret = 1;
    while (b > 0) {
        if (b & 1)
            ret = (ret * a) % MOD, b--;
        else
            a = (a * a) % MOD, b /= 2ll;
    }
    return ret;
}

void build(int l, int r, int k) {
    if (l == r) {
        tree[k] = y[l];
        return;
    }
    int m = (l + r) / 2;
    build(l, m, k * 2);
    build(m + 1, r, k * 2 + 1);
    tree[k] = max(tree[k * 2], tree[k * 2 + 1]);
}

void upd(int l, int r, int k, int a, ll val) {
    if (a < l || r < a)
        return;
    if (a <= l && r <= a) {
        tree[k] = val;
        return;
    }
    int m = (l + r) / 2;
    upd(l, m, k * 2, a, val);
    upd(m + 1, r, k * 2 + 1, a, val);
    tree[k] = max(tree[k * 2], tree[k * 2 + 1]);
}

ll qry(int l, int r, int k, int a, int b) {
    if (b < l || r < a)
        return 0;
    if (a <= l && r <= b)
        return tree[k];
    int m = (l + r) / 2;
    return max(qry(l, m, k * 2, a, b), qry(m + 1, r, k * 2 + 1, a, b));
}

set<pii> rng;

ll getAns() {
    auto it = rng.begin();
    ll cur = 1, y = qry(0, n - 1, 1, it->fi, it->se);
    ll prod = qry(n - 1);
    ll ans = (prod * y) % MOD;
    int cnt = 0;
    while (cur < INF && it != rng.end()) {
        cnt++;
        ll ny = qry(0, n - 1, 1, it->fi, it->se);
        if (cur * y < ny) {
            ans = (prod * pw(qry(it->fi - 1), MOD - 2) % MOD) * ny % MOD;
            cur = 1;
            y = ny;
        }
        cur *= 1ll * (ll) x[it->fi];
        it = next(it);
    }
    return ans;
}

int updateX(int pos, int val) {
    pos = n-pos-1;
    if (val == 1 && x[pos] != 1) {
        auto it = rng.lower_bound({pos, -1});
        pii nx = {pos, pos};
        auto a = it, b = it;
        pii flA = {-1, -1}, flB = {-1, -1};
        if (it != rng.begin()) {
            a = prev(a);
            if (x[a->fi] == 1) {
                nx.fi = a->fi;
                flA = {a->fi, a->se};
            }
        }
        if (it != (--rng.end())) {
            b = next(b);
            if (x[b->se] == 1) {
                nx.se = b->se;
                flB = {b->fi, b->se};
            }
        }
        rng.erase(it);
        if (flA.fi != -1)
            rng.erase(flA);
        if (flB.fi != -1)
            rng.erase(flB);
        rng.insert(nx);
    } else if (x[pos] == 1 && val != 1) {
        auto it = rng.lower_bound({pos, -1});
        pii nx = {pos, pos};
        if (it == rng.end() || it->fi > pos)
            it = prev(it);
        pii l = {it->fi, pos - 1};
        pii r = {pos + 1, it->se};
        rng.erase(it);
        if (l.fi <= l.se)
            rng.insert(l);
        if (r.fi <= r.se)
            rng.insert(r);
        rng.insert(nx);
    }
    ll up = val;
    up = (up * pw(x[pos], MOD - 2)) % MOD;
    upd(pos, up);
    x[pos] = val;
    return (int) getAns();
}

int updateY(int pos, int val) {
    pos = n-pos-1;
    ll up = val;
    up = (up * pw(y[pos], MOD - 2)) % MOD;
    upd(0, n - 1, 1, pos, val);
    y[pos] = val;
    return (int) getAns();
}

int init(int n, int x[], int y[]) {
    ::n = n;
    fill(BIT, BIT + n + 10, 1);
    pr[n] = 1;
    for (int i = 0; i < n; i++) {
        pr[n-i-1] = (pr[n-i] * 1ll * (ll) x[n-i-1]) % MOD;
        ::y[n-i-1] = y[i];
        ::x[n-i-1] = x[i];
        upd(n-i-1, x[i]);
    }
    for (int i = 0; i < n; i++) {
        int j = i;
        for (; j < n && ::x[j] == 1; j++);
        if (j != i)
            j--;
        rng.insert({i, j});
        i = j;
    }
    build(0, n - 1, 1);
    return (int) getAns();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'll getAns()':
horses.cpp:86:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
     ll cur = 1, y = qry(0, n - 1, 1, it->fi, it->se);
                 ^
horses.cpp:17:23: note: shadowed declaration is here
 ll pr[MAXN], x[MAXN], y[MAXN], tree[MAXN * 2], BIT[MAXN];
                       ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:161:33: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 int init(int n, int x[], int y[]) {
                                 ^
horses.cpp:17:23: note: shadowed declaration is here
 ll pr[MAXN], x[MAXN], y[MAXN], tree[MAXN * 2], BIT[MAXN];
                       ^
horses.cpp:161:33: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int init(int n, int x[], int y[]) {
                                 ^
horses.cpp:17:14: note: shadowed declaration is here
 ll pr[MAXN], x[MAXN], y[MAXN], tree[MAXN * 2], BIT[MAXN];
              ^
horses.cpp:161:33: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 int init(int n, int x[], int y[]) {
                                 ^
horses.cpp:18:5: note: shadowed declaration is here
 int n = 0;
     ^

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