Submission #1286542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286542		theiulius	Horses (IOI15_horses)	C++20	0 / 100	103 ms	27888 KiB

horses

#include<bits/stdc++.h>
// #include "horses.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
const int N = 5e2 + 5;
const int MOD = 1e9 + 7;
int tree[4 * N + 1];
int a[N], b[N];
int namr = 1, n = 0;
set<int> s;

int my_pow(int x, int y){
    // iterative fast power (modular)
    int64_t base = (x % MOD + MOD) % MOD;
    int64_t res = 1;
    int64_t exp = y;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return (int)res;
}

int my_div(int x){
    return my_pow(x, MOD - 2);
}

void update(int x, int l, int r, int pos, int val){
    b[pos] = val;
}

int get(int x, int l, int r, int tl, int tr){
    int ma = 0;
    for (int i = tl; i <= tr; i++){
        ma = max(ma, b[i]);
    }
    return ma;
}

int my_func(vector<int> x, vector<int> y){
    // x contains values (not positions). Use __int128 for safe product/comparison.
    __int128 pre = 1;
    __int128 best = 0;
    int ansi = 0;
    for (int i = 0; i < (int)x.size(); i++){
        pre *= (__int128)x[i];
        __int128 cand = pre * (__int128)y[i];
        if (cand > best){
            best = cand;
            ansi = i;
        }
    }

    return ansi;
}

int init(int n1, int x[], int y[]) {
    n = n1;
    for (int i = 0; i < n; i++){
        if (x[i] != 1){
            s.insert(i);
        }
    }

    for (int i = 0; i < n; i++){
        update(0, 0, n - 1, i, y[i]);
    }

    for (int i = 0; i < n; i++){
        a[i] = x[i];
        b[i] = y[i];
    }

    // mtlianis namr
    for (int i = 0; i < n; i++){
        namr *= x[i];
        namr %= MOD;
    }

    return 0;
}

int solve(){
    vector<int> x1, y1;
    auto it = s.end();
    it--;
    int suf = 1;
    while (suf < 1e9){
        // BUG FIX: multiply by value a[*it], not by the index *it
        suf *= a[*it];

        x1.pb(*it);

        if (it == s.begin()){
            break;
        }
        it--;
    }
    reverse(x1.begin(), x1.end());

    for (int i = 0; i < x1.size() - 1; i++){
        y1.pb(get(0, 0, n - 1, x1[i], x1[i + 1] - 1));
    }
    // (*x.rbegin(), n);
    y1.pb(get(0, 0, n - 1, (*x1.rbegin()), n - 1));

    // BUG FIX: my_func expects the a[] values, not positions.
    vector<int> vals;
    for (int pos : x1) vals.pb(a[pos]);

    int r = my_func(vals, y1);
    int ans = namr;
    for (int i = r + 1; i < x1.size(); i++){
        ans = ( (long long)ans * my_div(a[x1[i]]) ) % MOD;
    }
    if (ans < 0) ans += MOD;
    return ans;
}

int updateX(int pos, int val) {
    if (s.count(pos) && val == 1){
        s.erase(pos);
    }else if (!s.count(pos) && val != 1){
        s.insert(pos);
    }
    // namr-is shecvla
    namr = ( (long long)namr * my_div(a[pos]) ) % MOD;
    namr = ( (long long)namr * (val % MOD) ) % MOD;
    a[pos] = val;


    a[pos] = val;

    return solve();
}

int updateY(int pos, int val) {
    update(0, 0, n - 1, pos, val);

    return solve();
}

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