Submission #388230

#	Time	Username	Problem	Language	Result	Execution time	Memory
388230		ACmachine	Horses (IOI15_horses)	C++17	100 / 100	1361 ms	79044 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }

vector<int> X;
vector<int> Y;
set<int> non_one; // indices for comparison
const int mod = (int)1e9 + 7;

struct Mint{
    ll v;
    Mint(){v = 0;}
    Mint(ll _v) : v(_v){
        v %= mod;
        if(v < 0) v += mod;
    }
    friend Mint operator*(Mint a, Mint b){return Mint(a.v * b.v);}
    friend Mint operator+(Mint a, Mint b){a.v += b.v; if(a.v >= mod) a.v -= mod; return a;}
};



struct node{
    Mint segment_product;
    Mint result;
    int best_index = -1;
};
struct segtree{
    node comb(const node& a, const node& b){
        if(b.best_index == -1)
            return a;
        if(a.best_index == -1)
            return b;
        node res;
        res.segment_product = a.segment_product * b.segment_product;
        bool second_better = false;
        ll temp = Y[b.best_index];
        auto it = non_one.lower_bound(a.best_index + 1);
        for(;it != non_one.end(); ++it){
            if(*it > b.best_index) break;
            temp *= X[*it];
            if(temp >= Y[a.best_index]){
                second_better = true;
                break;
            }
        }
        if(temp >= Y[a.best_index])
            second_better = true;
        if(second_better){
            res.best_index = b.best_index;
            res.result = a.segment_product * b.result;
        }
        else{
            res.best_index = a.best_index;
            res.result = a.result;
        }
        return res;
    }
    int n;
    vector<node> tree;
    segtree(){}
    segtree(int _n){
        n = 1;
        while(n < _n) n *= 2;
        tree.resize(2 * n);
    }
    void build(vector<node> &init){
        REP(i, n){
            if(i < init.size())
                tree[i + n] = init[i];
        }
        FORD(i, n - 1, 1, 1)
            tree[i] = comb(tree[i << 1], tree[i << 1 | 1]);
    }
    void upd_index(int pos){ // no value needed, everything is up in arrays X and Y; those need to change
        pos += n;
        tree[pos].segment_product = Mint(X[pos - n]);
        tree[pos].result = Mint(X[pos - n]) * Mint(Y[pos - n]);
        for(int i = pos / 2; i > 0; i/=2)
            tree[i] = comb(tree[i << 1], tree[i << 1 | 1]);
    }
    int get_ans(){
        return tree[1].result.v;
    }
};
segtree st;

int init(int n, int Xin[], int Yin[]) {
    st = segtree(n);
    REP(i, n){
        X.pb(Xin[i]);
        Y.pb(Yin[i]);
    }
    vector<node> init(n);
    REP(i, n){
        init[i].best_index = i;
        init[i].result = Mint(X[i]) * Mint(Y[i]);
        init[i].segment_product = Mint(X[i]);
        if(X[i] > 1) non_one.insert(i);
    }
    st.build(init);
    /*
    FOR(i, 1, st.tree.size(), 1){
        dbg(st.tree[i].result.v, st.tree[i].best_index)
    }
     */
    //dbg(st.get_ans());

    return st.get_ans();
}

int updateX(int pos, int val) {
    X[pos] = val;
    if(X[pos] > 1)
        non_one.insert(pos);
    else
        non_one.erase(pos);
    st.upd_index(pos);
	return st.get_ans();
}

int updateY(int pos, int val) {
    Y[pos] = val;
    st.upd_index(pos);
	return st.get_ans();
}

Compilation message (stderr)

horses.cpp: In member function 'void segtree::build(std::vector<node>&)':
horses.cpp:122:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             if(i < init.size())
      |                ~~^~~~~~~~~~~~~
horses.cpp: In member function 'int segtree::get_ans()':
horses.cpp:136:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  136 |         return tree[1].result.v;

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