Submission #834217

#	Time	Username	Problem	Language	Result	Execution time	Memory
834217		ballbattle	Horses (IOI15_horses)	C++14	0 / 100	256 ms	52508 KiB

horses

#include "horses.h"
#include <iostream>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef set<ll> sll;

const ll modulo = 1000000007; // prime
const bool debug = false;

#define rep(a,b,c) for(ll a=b; a<c; a++)
#define rrep(a,b,c) for(ll a=c-1; a>=b; a--)
#define itr_rep(a,b,_type) for(_type::iterator a=b.begin(); a!=b.end(); a++)
#define ritr_rep(a,b,_type) for(_type::reverse_iterator a=b.rbegin(); a!=b.rend(); a++)
#define all(a) a.begin(),a.end()
#define sz(a) a.size()
#define pb(a) push_back(a)
#define db(x) if(debug){cout << x << endl;}

ll inverse(ll num); // mul inv mod modulo
ll find_max();
//int updateX(int pos, int val);
//int updateY(int pos, int val);
void build();
ll query(ll v, ll vl, ll vr, ll l, ll r);
void update(ll v, ll vl, ll vr, ll pos, ll val);

ll n;
ll m;
sll non_one;
ll prod;
vll x;
vll y;
vll x_inv;
vll y_op;
vll seg;

int init(int N, int X[], int Y[]) {
    prod = 1;
    n = N;
    x.resize(n,0);
    y.resize(n,0);
    x_inv.resize(n,0);
    y_op.resize(n,0);
    non_one.clear();
    rep(i,0,n) {x[i] = X[i];}
    rep(i,0,n) {y[i] = Y[i];}
    rep(i,0,n) {
        if (x[i] != 1) {
            non_one.insert(i); // nlogn but whatever.
        }
    }
    rep(i,0,n) {
        x_inv[i] = inverse(x[i]); // nlogn. eh
        prod = (prod*x[i]) % modulo;
    }

    // segtree time
    build();
    db("build done");
    non_one.insert(n); // for the benefit of the first element due to prev...
    for(sll::iterator itr = non_one.begin(); next(itr) != non_one.end(); itr++) {
        db(*itr);
        y_op[*itr] = query(1, 0, n-1, (*itr), (*next(itr))-1);
    }
    db("segtree done");
    if (debug) {
        rep(i,0,n) {cout << y_op[i] << " ";}
        cout << endl;
        rep(i,0,seg.size()) {cout << seg[i] << " ";}
        cout << endl;
    }

    return (int)find_max();
    //cout << find_max() << endl;

    /*ll val;
    ll pos;
    cin >> m;
    rep(i,0,m) {
        cin >> pos;
        cin >> val;
        cout << updateY(pos,val) << endl;
        //continue; // do things
    }

    if (debug) {
        rep(i,0,n) {cout << y_op[i] << " ";}
        cout << endl;
        rep(i,0,seg.size()) {cout << seg[i] << " ";}
        cout << endl;
    }*/

    //rep(i,0,n) {cout << x[i] << " " << x_inv[i] << " " << y[i] << endl;}
}


int updateX(int pos, int val) {
    if (val != 1) {
        if (x[pos] == 1) {
            sll::iterator itr = (non_one.insert(pos)).first;
            y_op[pos] = query(1,0,n-1,*itr,(*next(itr))-1);
            if (itr != non_one.begin()) {
                y_op[*prev(itr)] = query(1,0,n-1,*prev(itr),(*itr)-1);
            }
        }
    } else if (x[pos] != 1) {
        sll::iterator itr = non_one.erase(non_one.find(pos)); // gets the element after. Need the one before
        if (itr != non_one.begin()) {
            y_op[*prev(itr)] = max(y_op[*prev(itr)],y_op[pos]);
        }
    }
    prod = (prod*x_inv[pos]) % modulo;
    prod = (prod*val) % modulo;
    x[pos] = val;
    x_inv[pos] = inverse(val);
    return (int)find_max();
}

int updateY(int pos, int val) { // bruh
    y[pos] = val;
    update(1,0,n-1,pos,val);
    sll::iterator itr = non_one.upper_bound(pos); // exclusive range -> when prev -> inclusive downwards xdddddddddd
    if (itr != non_one.begin()) {
        y_op[*prev(itr)] = query(1,0,n-1,*prev(itr),(*itr)-1);
    }
    return (int)find_max();
}

ll inverse(ll num) { // modulo modulo - haha code it myself bc practice not perform nvm wikipedia it is
    ll old_r = modulo;
    ll r = num;
    //ll old_s = 1;
    //ll s = 0;
    ll old_t = 0;
    ll t = 1;
    ll q;

    while (r > 0) {
        q = old_r / r;
        old_r -= q*r;
        swap(r,old_r);
        //old_s -= q*s;
        //swap(s,old_s);
        old_t -= q*t;
        swap(t,old_t);
    }
    return (old_t + modulo) % modulo;
}

ll find_max() { // assume we have already updated
    ll best = 1; //
    ll new_prod = prod;
    for(sll::reverse_iterator itr = next(non_one.rbegin()); itr != non_one.rend(); itr++) {
        if (y_op[*itr] > best) {
            best = y_op[*itr];
        }

        new_prod = (new_prod*x_inv[*itr]) % modulo;
        best = best*x[*itr];
        db("b");
        db(*itr);
        db(x[*itr]);
        db(best);
        if (best > 1000000000) {return (best*new_prod) % modulo;}
    }
    return (best*new_prod) % modulo;
}

void build() {
    ll s = 1;
    for(ll i = n-1; i>0; i>>=1) {s <<= 1;}
    seg.resize(2*s,0);
    rep(i,0,s) {seg[s+i] = y[i];}
    rep(i,1,s+1) {seg[s-i] = max(seg[2*s - 2*i], seg[2*s - 2*i + 1]);}
}

ll query(ll v, ll vl, ll vr, ll l, ll r) {
    if (l>r) {return 0;}
    if ((l==vl) && (r==vr)) {return seg[v];}
    ll vm = (vl+vr)/2;
    return max(query(2*v,vl,vm,l,min(r,vm)),query(2*v+1,vm+1,vr,max(l,vm+1),r));
}

void update(ll v, ll vl, ll vr, ll pos, ll val) {
    if (vl==vr) {seg[v]=val;}
    else {
        ll vm = (vl+vr)/2;
        if (pos <= vm) {update(2*v,vl,vm,pos,val);}
        else {update(2*v+1,vm+1,vr,pos,val);}
        seg[v] = max(seg[2*v],seg[2*v+1]);
    }
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:15:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(a,b,c) for(ll a=b; a<c; a++)
......
   74 |         rep(i,0,seg.size()) {cout << seg[i] << " ";}
      |             ~~~~~~~~~~~~~~       
horses.cpp:74:9: note: in expansion of macro 'rep'
   74 |         rep(i,0,seg.size()) {cout << seg[i] << " ";}
      |         ^~~

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