Submission #1212318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212318		XCAC197	Horses (IOI15_horses)	C++20	100 / 100	735 ms	61112 KiB

horses

#include "horses.h"
#include <set>
#include <vector>
#include <iostream>
#define ll long long
using namespace std;

const int mod = 1000000007;

int N;
ll X [5000000];
ll Y [5000000];
ll seg [5000000];//max segtree
ll lc [5000000];//max segtree
ll rc [5000000];//max segtree
set <int, greater<int>> pos;
ll prod = 1;
int cnod = 5;
int root;

ll fpow(ll a, ll b){
    if(b == 0){
        return 1;
    }else{
        ll half = fpow(a, b/2);
        half = (half * half)%mod;
        if(b%2 == 1){
            half = (half * a)%mod;
        }
        return half;
    }
}
ll inv(ll a){
    return fpow(a, mod-2);
}

int nnod(){
    return cnod++;
}

int build(int cur, int l, int r){
    if(l == r){
        seg[cur] = Y[l];
    }else{
        lc[cur] = nnod();
        rc[cur] = nnod();
        build(lc[cur], l, (l+r)/2);
        build(rc[cur], (l+r)/2+1, r);
        seg[cur] = max(seg[lc[cur]], seg[rc[cur]]);
    }
    return cur;
}

void change(int cur, int l, int r, int x, int v){
    if(l <= x && x <= r){
        if(l == r){
            Y[x] = v;
            seg[cur] = v;
        }else{
            change(lc[cur], l, (l+r)/2, x, v);
            change(rc[cur], (l+r)/2+1, r, x, v);
            seg[cur] = max(seg[lc[cur]], seg[rc[cur]]);
        }
    }
}

ll getMax(int cur, int l, int r, int fl, int fr){
    if(fl <= l && r <= fr){
        return seg[cur];
    }else if(r < fl || fr < l){
        return 0;
    }else{
        return max(getMax(lc[cur], l, (l+r)/2, fl, fr), getMax(rc[cur], (l+r)/2+1, r, fl, fr));
    }
}


int query(){
    auto it = (pos.begin());
    vector <pair<ll, ll>> mva;
    ll div = 1;
    ll prv = N-1;
    while(true){
        int x = *(it);
      //  cerr << "?" <<  x << endl;
        mva.push_back(make_pair(getMax(root, 0, N-1, max(0, x), prv), div));
        prv = x-1;
        if(x == -1){
            break;
        }
        if(div * X[x] > 1000000000ll){
            break;
        }
        div *= X[x];
        it = next(it);
    }
  //  cerr << "DONE" << endl;
    ll ans = 0;
    for(int i = 0; i < mva.size(); i++){
        ans = max(ans, mva[i].first * div/mva[i].second);
    }
    ans = ans%mod;
    cerr << ans << endl;
    return (int)(((prod * ans)%mod * inv(div))%mod);
}

int init(int N_, int X_[], int Y_[]) {
    N = N_;
    for(int i = 0; i < N; i++){
        X[i] = X_[i];
        Y[i] = Y_[i];
    }
    pos.insert(-1);
    for(int i = 0; i < N; i++){
        if(X[i] > 1){
            //cerr << X[i] << " " << i << "   ";
            pos.insert(i);
            prod = (prod * X[i])%mod;
        }
    }
   // cerr << endl;
    root = build(nnod(), 0, N-1);
   // cerr << "INIT DONE" << endl;
    /*for(auto a : pos){
        cerr << (a) << " ";
    }
    cerr << endl;*/
    return query();
}

int updateX(int p, int v) {	
    pos.erase(p);
    prod = (prod * inv(X[p]))%mod;
    X[p] = v;
    if(v != 1){
        pos.insert(p);
    }
    prod = (prod * v)%mod;
    return query();
}

int updateY(int p, int v) {
    change(root, 0, N-1, p, v);
    return query();
}

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