Submission #533221

#	Time	Username	Problem	Language	Result	Execution time	Memory
533221		ivan24	Horses (IOI15_horses)	C++14	100 / 100	981 ms	88200 KiB

horses

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

using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

ll min (ll x, ll y){
    return ((x < y) ? x : y);
}

ll max (ll x, ll y){
    return ((x > y) ? x : y);
}

const ll INF = 1e18+10;
const ll MOD = 1e9+7;
const ll MX_VAL = 1e9;

struct stnode {
    ll prod,mx;
    stnode (){ prod = 1; mx = 0; }
    stnode merge_node (const stnode& rhs){
        stnode res;
        res.prod = prod*rhs.prod; res.prod %= MOD;
        res.mx = max(mx,rhs.mx);
        return res;
    }
};

ll modpow (ll b, ll e){
    ll res = 1;
    while (e > 0){
        if (e%2) res *= b;
        e /= 2; b *= b;
        res %= MOD; b %= MOD;
    }
    return res;
}

struct frac {
    ll n,d;
    frac(){ n = 1; d = 1;}
    frac (ll _n, ll _d){
        n = _n; d = _d;
    }
    bool operator>(const frac& rhs) const{
        return n*rhs.d > rhs.n*d;
    }
    bool operator<(const frac& rhs) const{
        return n*rhs.d < rhs.n*d;
    }
    ll mult (ll x){
        x *= n; x %= MOD;
        x *= modpow(d,MOD-2); x %= MOD;
        return x;
    }
};

class SegTree {
private:
    vector<stnode> st;
    ll n;
    vi a,b;
    ll left(ll x){ return (x << 1); }
    ll right(ll x){ return ((x << 1) + 1); }
    void build (ll i, ll l, ll r){
        if (l == r){
            st[i].prod = a[i];
            st[i].mx = b[i];
        }else{
            ll m = (l+r)/2;
            build(left(i),l,m);
            build(right(i),m+1,r);
            st[i] = st[left(i)].merge_node(st[right(i)]);
        }
    }
    stnode query (ll i, ll l, ll r, ll ql, ll qr){
        if (qr >= r && l >= ql){
            return st[i];
        }else if (l > qr || ql > r){
            return stnode();
        }else{
            ll m = (l+r)/2;
            stnode lres = query(left(i),l,m,ql,qr);
            stnode rres = query(right(i),m+1,r,ql,qr);
            return lres.merge_node(rres);
        }
    }
    void update (ll i, ll l, ll r, ll type, ll val, ll idx){
        //cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
        if (r >= idx && idx >= l){
            //cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
            if (r == l){
                if (type == 0) st[i].prod = val;
                else st[i].mx = val;
            }else{
                ll m = (l+r)/2;
                update(left(i),l,m,type,val,idx);
                update(right(i),m+1,r,type,val,idx);
                st[i] = st[left(i)].merge_node(st[right(i)]);
            }
        }
    }
public:
    SegTree (vi _a, vi _b): a(_a), b(_b){
        n = a.size();
        st.resize(4*n);
        build(1,0,n-1);
    }
    SegTree(ll _n){
        n = _n;
        a.assign(n,1);
        b.assign(n,0);
        st.assign(4*n,stnode());
    }
    SegTree(){}
    ll query (ll type, ll l, ll r){
        stnode res;
        //cout << "queried: " << type << " " << l << " " << r << endl;
        if (r >= l) res = query(1,0,n-1,l,r);
        if (type == 0) return res.prod;
        else return res.mx;
    }
    void update (ll type, ll val, ll idx){
        //cout << "update: " << type << " " << val << " " << idx << endl;
        //cout << n << endl;
        update (1,0,n-1,type,val,idx);
    }
};

class WeirdDS {
private:
    SegTree st;
    vi x,y;
    set<ll> overone;
    ll n;
public:
    WeirdDS(int _n){
        n = _n;
        st = SegTree(n);
        x.assign(n,1);
        y.assign(n,0);
        set<ll>().swap(overone);
        overone.insert(0);
    }
    WeirdDS(){}
    void updateX(ll pos, ll val){
        st.update(0,val,pos);
        if (val == 1){
            auto itr = overone.find(-pos);
            if (itr != overone.end())
                overone.erase(itr);
        }else{
            overone.insert(-pos);
        }
        overone.insert(0);
        x[pos] = val;
    }
    void updateY(ll pos, ll val){
        st.update(1,val,pos);
    }
    ll query (){
        bool broke = false;
        ll prv = n;
        ll ctr = 1;
        frac maxMult;
        for (auto i: overone){
            ll bigY = st.query(1,-i,prv-1);
            frac curMult = frac(bigY,ctr);
            if (curMult > maxMult) maxMult = curMult;
            prv = -i;
            ctr *= x[-i];
            if (x[-i] == 1 && i != 0) return INF;
            if (ctr > MX_VAL) break;
        }
        return maxMult.mult(st.query(0,0,n-1));
    }
};

WeirdDS myDS;

int init(int n, int x[], int y[]) {
    //cout.setstate(ios_base::failbit);
    myDS = WeirdDS(n);
    for (ll i = 0; n > i; i++){
        myDS.updateX(i,x[i]);
        myDS.updateY(i,y[i]);
    }
    ////cout << myDS.query() << endl;
	return myDS.query();
}

int updateX(int pos, int val) {
    //cout << "updateX: " << pos << " " << val << endl;
    myDS.updateX(pos,val);
    //cout << res << endl;
	return myDS.query();
}

int updateY(int pos, int val) {
    //cout << "updateY: " << pos << " " << val << endl;
    myDS.updateY(pos,val);
    //cout << res << endl;
	return myDS.query();
}

Compilation message (stderr)

horses.cpp: In member function 'll WeirdDS::query()':
horses.cpp:170:14: warning: unused variable 'broke' [-Wunused-variable]
  170 |         bool broke = false;
      |              ^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:197:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  197 |  return myDS.query();
      |         ~~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:204:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  204 |  return myDS.query();
      |         ~~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:211:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  211 |  return myDS.query();
      |         ~~~~~~~~~~^~

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