Submission #1065540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065540		anango	Horses (IOI15_horses)	C++17	17 / 100	35 ms	41840 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

int MOD = 1000000007;
int INF = 1LL<<60;

//maintain a set of all indices such that X[i]>1
//consider the last 30 such indices
//then using a max segtree calculate the maximum Y[i] in between these indices, and thus compute the max X[i]*Y[i] at that index
//we can compute the prefix products of the X[i] using another segtree, which allows us to make point updates
//and range product queries

int exp(int base, int exponent) {
    int t = base;
    int p = 1;
    for (int i=0; i<32; i++) {
        if (exponent&(1LL<<i)) {
            p*=t; p%=MOD;
        }
        t*=t;
        t%=MOD;
    }
    return p;
}

int inv(int base) {
    return exp(base,MOD-2);
}

class productSegTree {
public:
    const int sz = 1048576;
    vector<int> tree;
    productSegTree() {
        tree=vector<int>(sz,1);
    }
    //each node carries the product of its children
    void update(int v, int l, int r, int tl, int tr, int assignment) {
        if (l>tr || r<tl) return;
        if (l<=tl && tr<=r) {
            tree[v]=assignment;
            tree[v]%=MOD;
            return;
        }
        int m = (tl+tr)/2;
        update(2*v,l,r,tl,m,assignment);
        update(2*v+1,l,r,m+1,tr,assignment);
        tree[v] = tree[2*v]*tree[2*v+1];
        tree[v]%=MOD;
    }
    int query(int v, int l, int r, int tl, int tr) {
        if (l>tr || r<tl) return 1;
        if (l<=tl && tr<=r) {
            return tree[v];
        }
        int m = (tl+tr)/2;
        int a = query(2*v,l,r,tl,m);
        int b = query(2*v+1,l,r,m+1,tr);
        return (a*b)%MOD;
    }

    void update_wrapper(int index, int mult) {
        update(1,index,index,0,sz/2-1,mult);
    }
    int query_wrapper(int index) {
        //0...index
        return query(1,0,index,0,sz/2-1);
    }
};

class maxSegTree {
public:
    const int sz = 1048576;
    vector<int> tree;
    maxSegTree() {
        tree=vector<int>(sz,0);
    }
    //each node carries the max of its children
    void update(int v, int l, int r, int tl, int tr, int assignment) {
        if (l>tr || r<tl) return;
        if (l<=tl && tr<=r) {
            tree[v]=assignment;
            return;
        }
        int m = (tl+tr)/2;
        update(2*v,l,r,tl,m,assignment);
        update(2*v+1,l,r,m+1,tr,assignment);
        tree[v] = max(tree[2*v],tree[2*v+1]);
    }
    int query(int v, int l, int r, int tl, int tr) {
        if (l>tr || r<tl) return -INF;
        if (l<=tl && tr<=r) {
            return tree[v];
        }
        int m = (tl+tr)/2;
        int a = query(2*v,l,r,tl,m);
        int b = query(2*v+1,l,r,m+1,tr);
        return max(a,b);
    }
    void update_wrapper(int index, int assignment) {
        update(1,index,index,0,sz/2-1,assignment);
    }
    int query_wrapper(int l, int r) {
        return query(1,l,r,0,sz/2-1);
    }
};

set<int> usefulX;
vector<int> xval,yval;
maxSegTree yseg;
productSegTree xseg;
int n;

signed get_answer() {
    vector<int> needcheck={0};
    auto it = usefulX.end();
    for (int i=0; i<32; i++) {
        if (it==usefulX.begin()) break;
        it--;
        int r = *it;
        needcheck.push_back(r);
    }
    needcheck.push_back(n);
    sort(needcheck.begin(), needcheck.end());
    int answer = -1;
    int suffprod = 1;
    int bestyval = 0;
    int bestsuffprod = 1;
    //want maximum value of maxyval / suffprod
    int k = needcheck.size();
    for (int i=k-2; i>=0; i--) {
        if (suffprod>1073741824) break;
        int maxyval = yseg.query_wrapper(needcheck[i],needcheck[i+1]-1);
        if (maxyval*bestsuffprod>bestyval*suffprod) {
            //cout << "changed " << i << " " << maxyval <<" " << bestsuffprod <<" " << bestyval <<" " << suffprod << endl;
            bestsuffprod = suffprod;
            bestyval = maxyval;
            answer = maxyval*xseg.query_wrapper(needcheck[i]); 
            answer%=MOD;
        }
        //cout << "trying " << i <<" " << needcheck[i] <<" " << needcheck[i+1] <<" " << maxyval <<" " << suffprod << " " << maxyval*xseg.query_wrapper(needcheck[i]) << endl;

        suffprod*=xval[needcheck[i]];
    }
    return (signed)answer;

}

signed init(signed N, signed X[], signed Y[]) {
    n=N;
    assert(n<11);
    xval=yval=vector<int>(N,0);
    for (int i=0; i<N; i++) {
        xval[i] = X[i]; yval[i] = Y[i];
        if (xval[i]!=1) usefulX.insert(i);
    }
    for (int i=0; i<N; i++) {
        xseg.update_wrapper(i,X[i]);
        yseg.update_wrapper(i,Y[i]);
    }
	return get_answer();
}

signed updateX(signed pos, signed val) {
    xval[pos] = val;	
    xseg.update_wrapper(pos,val);
	return get_answer();
}

signed updateY(signed pos, signed val) {
    yval[pos] = val;
    yseg.update_wrapper(pos,val);
	return get_answer();
}

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