Submission #1086315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086315		RiverFlow	Horses (IOI15_horses)	C++14	37 / 100	442 ms	55024 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)


const int N = (int)5e5 + 7;

const int mod = (int)1e9 + 7;

int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
int sub(int a, int b) { return a >= b ? a - b : a - b + mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

int Pow(int a, long long b) {
    int res = 1;
    for(; b > 0; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) res = 1ll * res * a % mod;
    return res;
}
int n, x[N], y[N];

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define nl "\n"
#define ll long long

const ll LIM = (int)1e10;

struct ST {
    int n;
    vector<int> t;
    ST () {};
    ST (int _n) {
        n = _n;
        t.resize(4 * n + 7);
    }
    int comb(int a, int b) {
        return y[a - 1] >= y[b - 1] ? a : b;
    }
    void build(int id, int l, int r) {
        if (l == r) return void(t[id] = l);
        int m = (l + r) >> 1;
        build(id << 1, l, m);
        build(id << 1 | 1, m + 1, r);
        t[id] = comb(t[id << 1], t[id << 1 | 1]);
    }
    int get(int id, int l, int r, int u, int v) {
        if (l > v or r < u) return 0;
        if (l >= u and r <= v) return t[id];
        int m = (l + r) >> 1;
        return comb(get(id << 1, l, m, u, v),
                    get(id << 1 | 1, m + 1, r, u, v));
    }
    int get(int l, int r) {
        return get(1, 1, n, l + 1, r + 1);
    }
    void upd(int id, int l, int r, int p) {
        if (l == r) return ;
        int m = (l + r) >> 1;
        if (p <= m)
            upd(id << 1, l, m, p);
        else
            upd(id << 1 | 1, m + 1, r, p);
        t[id] = comb(t[id << 1], t[id << 1 | 1]);
    }
    void upd(int p) {
        upd(1, 1, n, p + 1);
    }
};

struct FW {
    int n;
    vector<int> bit;
    FW () {};
    FW (int _n) {
        n = _n;
        bit.assign(n + 1, 1);
    }
    void build() {
        FOR(i, 1, n) {
            for(int j = i; j <= n; j += j & -j)
                bit[j] = mul(bit[j], x[i - 1]);
        }
    }
    void upd(int id, int v) {
        ++id;
        for(; id <= n; id += id & -id)
            bit[id] = mul(bit[id], v);
    }
    int get(int id) {
        ++id;
        int res = 1;
        for(; id > 0; id -= id & -id)
            res = mul(res, bit[id]);
        return res;
    }
};

int fx() {
    ll mx = 0;
    int ans = 0;
    FOD(i, n - 1, 0) {
        if (y[i] >= mx) {
            ans = i;
        }
        mx = max(mx, (ll)y[i]);
        mx = min(LIM, mx * x[i]);
    }
    return ans;
}

set<int> posi; // left
vector<int> ones; // right
const int B = 30;

ST st;
FW fw;

int last_res = 0;

int calc() {
    if (sz(ones) == 0) {
        return y[ st.t[1] - 1 ];
    }
    vector<int> px;
    bool ins = 0;
    if (ones[0] > 0)
        px.push_back(st.get(0, ones[0] - 1)), ins = 1;
    for(int i = 0; i < sz(ones) - 1; ++i) {
        px.push_back(st.get(ones[i], ones[i + 1] - 1));
    }
    px.push_back(st.get(ones.back(), n - 1));

    // co duoc vi tri max y roi
    // co duoc cac px
    // tim vi tri px nho nhat thoi
    int ans = -1;
    ll mx = 0;
    FOD(j, sz(px) - 1, 0) {
        int i = px[j] - 1;
        if (y[i] >= mx) {
            ans = i;
        }
        mx = max(mx, (ll)y[i]);
        if (ins) {
            if (j > 0)
                mx = min(LIM, mx * x[ones[j - 1]]);
        } else {
            mx = min(LIM, mx * x[ones[j]]);
        }
    }
//    cout << "ones: ";
//    for(int x : ones) cout << x << ' '; cout << nl;
//    cerr << ans << nl;
//    assert(ans != -1);
    int t = fw.get(ans);
    return mul(y[ans], t);
}

int init(int N, int X[], int Y[]) {
    n = N;

    FOR(i, 0, n - 1) x[i] = X[i], y[i] = Y[i];

    st = ST(n);
    fw = FW(n);

    st.build(1, 1, n);

    fw.build();

    FOD(i, n - 1, 0) {
        if (x[i] > 1) {
            if (sz(ones) < B) ones.push_back(i);
            else posi.insert(i);
        }
    }
    reverse(ones.begin(), ones.end());

//    for(int j : ones) cout << j << ' '; cout << nl;

    return calc();
}
vector<int> nw;

int updateX(int pos, int val) {
    // handle mot so viec tu >1, -> =1
    if (x[pos] == val) return calc();
    if (sz(nw)) nw.clear();

    if (x[pos] == 1) {
        // vi tri dau tien ma pos >
        if (sz(ones) == 0) {
            ones.push_back(pos);
        } else {
            // size no lon hon 1
            // xet vi tri dau tien no nho hon thoi
            bool ins = 0;
            FOR(i, 0, sz(ones) - 1) {
                if (ones[i] > pos and !ins) {
                    nw.push_back(pos);
                    ins = 1;
                }
                nw.push_back(ones[i]);
            }
            if (!ins) nw.push_back(pos);
            if (sz(nw) <= B) {
                ones = nw;
            } else {
                reverse(all(ones));
                posi.insert(ones.back());
                ones.pop_back();
                reverse(all(ones));
            }
        }
    } else if (x[pos] > 1 and val == 1) {
        // handle delete
        if (posi.find(pos) != posi.end()) {
            posi.erase(pos);
        } else {
            // nam trong day
            if (sz(posi)) {
                nw.push_back(*posi.rbegin());
                posi.erase(*posi.rbegin());
            }
            FOR(i, 0, sz(ones) - 1) if (ones[i] != pos)
                nw.push_back(ones[i]);
            swap(nw, ones);
        }
    }

    fw.upd(pos, mul(val, Pow(x[pos], mod - 2)));

    x[pos] = val;

    return calc();
}

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

Compilation message (stderr)

horses.cpp: In function 'int mul(int, int)':
horses.cpp:17:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 | int mul(int a, int b) { return 1LL * a * b % mod; }
      |                                ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int Pow(int, long long int)':
horses.cpp:21:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   21 |     for(; b > 0; b >>= 1, a = 1ll * a * a % mod)
      |                               ~~~~~~~~~~~~^~~~~
horses.cpp:22:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |         if (b & 1) res = 1ll * res * a % mod;
      |                          ~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:165:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  165 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:11:11: note: shadowed declaration is here
   11 | const int N = (int)5e5 + 7;
      |           ^

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