Submission #594464

#	Time	Username	Problem	Language	Result	Execution time	Memory
594464		davi_bart	Horses (IOI15_horses)	C++14	100 / 100	839 ms	90980 KiB

horses

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#include "horses.h"
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
static const int mod = 1e9 + 7;
int pot(int a, int b) {
    if (b == 0) return 1;
    int x = pot(a, b / 2);
    if (b % 2) return x * x % mod * a % mod;
    return x * x % mod;
}
struct segment {
    static const int dim = 1 << 19;
    struct node {
        ld log = 0;
        int mod = 1;
        ld lazy_log = 0;
        int lazy_mod = 1;
    };
    vector<node> s = vector<node>(2 * dim);
    void prop(int pos) {
        if (s[pos].lazy_log != 0) {
            s[pos].log += s[pos].lazy_log;
            if (pos < dim) {
                s[2 * pos].lazy_log += s[pos].lazy_log;
                s[2 * pos + 1].lazy_log += s[pos].lazy_log;
            }
            s[pos].lazy_log = 0;
        }
        if (s[pos].lazy_mod > 1) {
            s[pos].mod = s[pos].mod * s[pos].lazy_mod % mod;
            if (pos < dim) {
                s[2 * pos].lazy_mod = s[2 * pos].lazy_mod * s[pos].lazy_mod % mod;
                s[2 * pos + 1].lazy_mod = s[2 * pos + 1].lazy_mod * s[pos].lazy_mod % mod;
            }
            s[pos].lazy_mod = 1;
        }
    }
    void upd(int pos, int l, int r, int a, int b, ld log_, int mod_) {
        prop(pos);
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            s[pos].lazy_log += log_;
            s[pos].lazy_mod = s[pos].lazy_mod * mod_ % mod;
            prop(pos);
            return;
        }
        int m = (l + r) / 2;
        upd(2 * pos, l, m, a, b, log_, mod_);
        upd(2 * pos + 1, m + 1, r, a, b, log_, mod_);

        if (s[2 * pos].log > s[2 * pos + 1].log)
            s[pos] = s[2 * pos];
        else
            s[pos] = s[2 * pos + 1];
    }
    void upd(int a, int b, ld log_, int mod_) {
        upd(1, 0, dim - 1, a, b, log_, mod_);
    }
    int query() {
        prop(1);
        // cout << s[1].log << " " << s[1].lazy_mod << " " << s[1].lazy_log << endl;
        return s[1].mod;
    }

} seg;
vector<int> X, Y;
int N;
int calc() {
    int ma = 0;
    int cur = 1;
    for (int i = 0; i < N; i++) {
        cur *= X[i];
        ma = max(ma, cur * Y[i] % mod);
    }
    return ma;
}
signed init(signed N, signed x[], signed y[]) {
    ::N = N;
    for (int i = 0; i < N; i++) {
        X.pb(x[i]);
        Y.pb(y[i]);
        seg.upd(i, N, log(X[i]), X[i]);
        seg.upd(i, i, log(Y[i]), Y[i]);
    }
    return seg.query();
}

signed updateX(signed pos, signed val) {
    seg.upd(pos, N, -log(X[pos]) + log(val), val * pot(X[pos], mod - 2) % mod);
    X[pos] = val;
    // seg.upd(pos, N, log(val), val);
    return seg.query();
}

signed updateY(signed pos, signed val) {
    seg.upd(pos, pos, -log(Y[pos]) + log(val), pot(Y[pos], mod - 2) * val % mod);
    Y[pos] = val;
    // seg.upd(pos, pos, log(val), val);
    return seg.query();
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:86:20: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   86 | signed init(signed N, signed x[], signed y[]) {
      |             ~~~~~~~^
horses.cpp:76:5: note: shadowed declaration is here
   76 | int N;
      |     ^
horses.cpp:94:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   94 |     return seg.query();
      |            ~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:101:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |     return seg.query();
      |            ~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:108:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  108 |     return seg.query();
      |            ~~~~~~~~~^~

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