Submission #726483

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
726483	2023-04-19T02:58:14 Z	becaido	Horses (IOI15_horses)	C++17	Compilation error	0 ms	0 KB

horses

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "horses.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int MOD = 1e9 + 7;
const int SIZE = 5e5 + 5;

struct Node {
    int pro = 1;
    double sum = 0, mx = 0;
    Node operator + (const Node& rhs) const {
        Node re;
        re.pro = 1ll * pro * rhs.pro % MOD;
        re.sum = sum + rhs.sum;
        re.mx = max(mx, sum + rhs.mx);
        return re;
    }
} node[4 * SIZE];

int n, y[SIZE];

void upd(int pos, int l, int r, int p, int ty, int x) {
    if (l == r) {
        if (ty == 1) {
            node[pos].pro = x;
            node[pos].sum = log(x);
        }
        if (ty == 2) {
            node[pos].mx = log(y[p] = x);
        }
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) upd(lpos, l, mid, p, ty, x);
    else upd(rpos, mid + 1, r, p, ty, x);
    node[pos] = node[lpos] + node[rpos];
}

int que(int pos, int l, int r, int cur = 1) {
    if (l == r) return 1ll * cur * y[l] % MOD;
    int mid = (l + r) / 2;
    if (node[lpos].mx >= node[lpos].sum + node[rpos].mx) return que(lpos, l, mid, cur);
    else return que(rpos, mid + 1, r, 1ll * cur * node[lpos].pro % MOD);
}

int init(int N, int X[], int Y[]) {
    auto build = [&](auto build, int pos, int l, int r)->void {
        if (l == r) {
            node[pos].pro = X[l];
            node[pos].sum = log(X[l]);
            node[pos].mx = log(y[l] = Y[l]);
            return;
        }
        int mid = (l + r) / 2;
        build(build, lpos, l, mid);
        build(build, rpos, mid + 1, r);
        node[pos] = node[lpos] + node[rpos];
    };
    n = N;
    build(build, 1, 0, n - 1);
    return que(1, 0, n - 1);
}

int updateX(int pos, int val) {
    upd(1, 0, n - 1, pos, 1, val);
    return que(1, 0, n - 1);
}

int updateY(int pos, int val) {
    upd(1, 0, n - 1, pos, 2, val);
    return que(1, 0, n - 1);
}

/*
in1
3
2 1 3
3 4 1
1
2 1 2
out1
...
*/

#ifdef WAIMAI
int main() {
    int N; cin >> N;

    int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
    int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);

    for (int i = 0; i < N; i++) cin >> X[i];

    for (int i = 0; i < N; i++) cin >> Y[i];

    cout << init(N,X,Y) << '\n';

    int M; cin >> M;
    for (int i = 0; i < M; i++) {
        int type; cin >> type;
        int pos; cin >> pos;
        int val; cin >> val;

        if (type == 1) {
            cout << updateX(pos,val) << '\n';
        } else if (type == 2) {
            cout << updateY(pos,val) << '\n';
        }
    }

    return 0;
}
#endif

Compilation message

Compilation timeout while compiling horses