Submission #1219000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219000		LIA	말 (IOI15_horses)	C++17	100 / 100	230 ms	53860 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <ll,ll,ll> plll;
typedef vector <plll> vplll;
typedef pair <ll,ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <vector <pll>> vvpll;
typedef vector <vector <ll>> vvll;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;

vll seg;
vector<double> xlog, ylog;
vll X, Y;
ll n;
ll sz=1;

vector<double> seg2, lazy2;
vector<ll> idx2;

void build() {
    for (; sz<n; sz*=2);
    seg.assign(2*sz, 1);
    loop(i,0,n) seg[sz+i] = X[i];
    loop(i,sz+n,2*sz) seg[i] = 1;
    loopr(i,sz,1) seg[i] = (seg[2*i] * seg[2*i+1]) % inf;
}

void update(ll p, ll val) {
    ll pos = sz + p;
    seg[pos] = val;
    for (pos/=2; pos>0; pos/=2) seg[pos] = (seg[2*pos] * seg[2*pos+1]) % inf;
}

ll query(ll rr) {
    ll l = sz, r = sz + rr;
    ll ans = 1;
    while (l <= r) {
        if (l%2 == 1) ans = (ans * seg[l++]) % inf;
        if (r%2 == 0) ans = (ans * seg[r--]) % inf;
        l/=2;
        r/=2;
    }
    return ans;
}

void push2(ll p) {
    if (lazy2[p] != 0) {
        lazy2[2*p] += lazy2[p]; seg2[2*p] += lazy2[p];
        lazy2[2*p+1] += lazy2[p]; seg2[2*p+1] += lazy2[p];
        lazy2[p] = 0;
    }
}

void pull2(ll p) {
    if (seg2[2*p] >= seg2[2*p+1]) {
        seg2[p] = seg2[2*p]; idx2[p] = idx2[2*p];
    } else {
        seg2[p] = seg2[2*p+1]; idx2[p] = idx2[2*p+1];
    }
}

void build2() {
    seg2.assign(2*sz, 0);
    lazy2.assign(2*sz, 0);
    idx2.assign(2*sz, 0);
    double cur = 0;
    loop(i,0,n) {
        cur += xlog[i];
        seg2[sz+i] = cur + ylog[i];
        idx2[sz+i] = i;
    }
    loop(i,sz+n,2*sz) {
        seg2[i] = -1e300;
        idx2[i] = i - sz;
    }
    loopr(i,sz,1) pull2(i);
}

void rangeAdd(ll l, ll r, double v, ll p, ll lb, ll rb) {
    if (r < lb || rb < l) return;
    if (l <= lb && rb <= r) {
        seg2[p] += v;
        lazy2[p] += v;
        return;
    }
    push2(p);
    ll m = (lb + rb) / 2;
    rangeAdd(l, r, v, 2*p, lb, m);
    rangeAdd(l, r, v, 2*p+1, m+1, rb);
    pull2(p);
}

ll getIdx() {
    return idx2[1];
}

int init(int N, int X1[], int Y1[]) {
    n = N;
    xlog.resize(n);
    ylog.resize(n);
    X.resize(n);
    Y.resize(n);
    loop(i,0,n) {
        xlog[i] = log2((double)X1[i]);
        ylog[i] = log2((double)Y1[i]);
        X[i] = X1[i];
        Y[i] = Y1[i];
    }
    build();
    build2();
    ll idx = getIdx();
    ll ansi = query(idx);
    ansi = (ansi * Y[idx]) % inf;
    return ansi;
}

int updateX(int pos, int val) {
    double delta = log2((double)val) - xlog[pos];
    xlog[pos] += delta;
    X[pos] = val;
    update(pos, val);
    rangeAdd(pos, n-1, delta, 1, 0, sz-1);
    ll idx = getIdx();
    ll ansi = query(idx);
    ansi = (ansi * Y[idx]) % inf;
    return ansi;
}

int updateY(int pos, int val) {
    double delta = log2((double)val) - ylog[pos];
    ylog[pos] += delta;
    Y[pos] = val;
    rangeAdd(pos, pos, delta, 1, 0, sz-1);
    ll idx = getIdx();
    ll ansi = query(idx);
    ansi = (ansi * Y[idx]) % inf;
    return ansi;
}

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