Submission #795482

#	Time	Username	Problem	Language	Result	Execution time	Memory
795482		Markynoodle	Horses (IOI15_horses)	C++17	17 / 100	315 ms	106096 KiB

horses

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

#define all(x) x.begin(),x.end()
#define ll long long
#define fastOI ios_base::sync_with_stdio(false); cin.tie(nullptr);
auto cmp = [](int a, int b){return a > b;};
auto cmp1 = [](pair<ll,ll> a, pair<ll,ll> b){return a.second < b.second;};
ll mod = 1000000007;


vector<ll> segtreex;
vector<ll> segtreey;

void updatex(int l, int r, int pos, int ind, ll x){

    int m = l + (r - l)/2;
    if(ind < l || ind >= r)return;
    if(l == ind && l + 1 == r){
        segtreex[pos] = x;
        return;
    }
    updatex(l, m, pos*2, ind, x);
    updatex(m, r, pos*2 + 1, ind, x);
    segtreex[pos] = (segtreex[pos*2] * segtreex[pos*2 + 1])%mod;
    return;
}

ll queryx(int l, int r, int pos, int ql, int qr){
    if( ql <= l && qr >= r)return segtreex[pos];
    if( qr <= l || ql >= r)return 1;
    int m = l + (r-l)/2;
    return (queryx(l, m, pos * 2, ql, qr) * queryx(m, r, pos*2 + 1, ql, qr))%mod;
}

void updatey(int l, int r, int pos, int ind, ll x){
    int m = l + (r - l)/2;
    if(ind < l || ind >= r)return;
    if(l == ind && l + 1 == r){
        segtreey[pos] = x;
        return;
    }
    updatey(l, m, pos*2, ind, x);
    updatey(m, r, pos*2 + 1, ind, x);
    segtreey[pos] = max(segtreey[pos*2], segtreey[pos*2 + 1]);
    return;
}

ll queryy(int l, int r, int pos, int ql, int qr){

    if( ql <= l && qr >= r)return segtreey[pos];
    if( qr <= l || ql >= r)return 0;
    int m = l + (r-l)/2;
    return max(queryy(l, m, pos * 2, ql, qr), queryy(m, r, pos*2 + 1, ql, qr));
}

set<ll> fasts;
int npo2;
vector<ll> g;
vector<ll> p;
int n;

ll solve(){

    if(fasts.empty()){
        return queryy(0, npo2, 1, 0, npo2);
    }
    vector<pair<ll,ll>> solver(30,{1, 1});
    set<ll>::iterator pt = fasts.end();
    int opt = (min(30, int(fasts.size())));
    int last = n;
    ll temppro = 1;
    for(int i = 0 ;i < opt; i++){
        pt--;
        solver[opt - i].first = g[*pt]; // if need be -1 on index
        solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
        //cout<<g[*pt]<<" "<<*pt<<" "<<last<<" "<<solver[opt - i].second<<"\n";
        last = *pt;
        temppro *= g[*pt];
        if(temppro >= mod)break;
    }
    ll startproduct = queryx(0, npo2, 1, 0, last);
    temppro = 1;
    ll best = 1;
    for(int i = 0; i <= opt; i++){
        temppro *= solver[i].first;
        //cout<<temppro<<" "<<temppro * solver[i].second<<"_ ";
        best = max(best, temppro * solver[i].second);
    }
    best %= mod;
    return (best * startproduct)%mod;

    //x for growth
    // y for prices;
}
int init(int nn, int xx[], int yy[]){
    for(int i = 0; i<nn; i++){
        g.push_back(xx[i]);
        p.push_back(yy[i]);
    }

    n = nn;
    npo2 = __lg(n-1) + 1;
    npo2 = (1<<npo2);
    segtreex.resize(npo2 * 2, 1);
    segtreey.resize(npo2 * 2, 0);
    for(int i = 0; i<n; i++){
        if(g[i] > 1){
            updatex(0, npo2, 1, i, g[i]);
        }
        if(g[i] > 1)fasts.insert(i);
    }
    for(int i = 0; i<n; i++){
        updatey(0, npo2, 1, i, p[i]);
    }
    return solve();
}




int updateX(int pos, int val) {	
    updatex(0, npo2, 1, pos, val);
    if(val == 1){
        fasts.erase(pos);
    }
    else fasts.insert(pos);
    g[pos] = val;
	return solve();
}

int updateY(int pos, int val) {
    updatey(0, npo2, 1, pos, val);
    p[pos] = val;
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'long long int solve()':
horses.cpp:77:53: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |         solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
      |                                                     ^~~
horses.cpp:79:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |         last = *pt;
      |                ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:117:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  117 |     return solve();
      |            ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:130:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  130 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:136:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  136 |  return solve();
      |         ~~~~~^~

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