Submission #343360

#	Time	Username	Problem	Language	Result	Execution time	Memory
343360		bigDuck	Horses (IOI15_horses)	C++14	100 / 100	742 ms	41196 KiB

horses

#include "horses.h"

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

ll mod=((ll)1e9)+7;
int N;
ll exp(ll x, ll e){
    if(e==1){
        return x%mod;
    }
    if(e==0){
        return 1;
    }
    return (exp(x, e%2)*exp( (x*x)%mod, e/2))%mod;
}

ll inv(ll x){
    return exp(x, mod-2);
}



ll prod=1ll;
multiset<pii> suf;


int x[500010], y[500010];
int seg[2000010];


void build_seg(int v, int tl, int tr){
    if(tl==tr){
        seg[v]=y[tl];
        return;
    }
    int mid=(tl+tr)>>1ll;
    build_seg(2*v, tl, mid); build_seg(2*v+1, mid+1, tr);
    seg[v]=max(seg[2*v], seg[2*v+1]);
    return;
}


void update_seg(int v, int tl, int tr, int pos, int x){

    if(tl==tr){
        seg[v]=x;
        y[tl]=x;
        return;
    }
    int mid=(tl+tr)>>1ll;
    if(pos<=mid){
        update_seg(2*v, tl, mid, pos, x);
    }
    else{
        update_seg(2*v+1, mid+1, tr, pos, x);
    }
    seg[v]=max(seg[2*v], seg[2*v+1]);
    return;
}

int query(int v, int tl, int tr, int l, int r){
    if(l>r){
        return 0;
    }
    if( (tl==l) && (tr==r) ){
        return seg[v];
    }
    int mid=(tl+tr)>>1ll;
    int q1=query(2*v, tl, mid, l, min(r, mid)), q2=query(2*v+1, mid+1, tr, max(l, mid+1), r);
    return max(q1, q2);
}





int get_resp(int N){
    ll prod2=1ll;
    ll prod3=1ll;
    ll prod1=1ll;
    ll res=y[N];
    auto it=suf.end();
    ll lt=N;

    if(it==suf.begin()){
        res=query(1, 1, N, 1, lt);
        return (res*prod)%mod;
    }
    it--;
    int cnt=0;
    for(;;it--){
        ll pos=it->ft, X=it->sc;
        ll Y=query(1, 1, N, pos, lt);
        if( (  ( ( (res*prod3)%mod  )*((prod1) ) )  )<Y  ){
            //cout<<res<<" "<<((res*prod2)%mod)<<" "<<Y<<" "<<prod<<"\n";
            res=(Y*inv(prod2))%mod;
            prod3=prod2;
            prod1=1ll;
            cnt++;
        }
        lt=pos-1;

        prod2*=X;
        prod1*=X;
        if(prod2>=((ll)1e9)){
            break;
        }
        if(it==suf.begin()){
            break;
        }
    }
    if( (prod2<((ll)1e9)) && (lt>0) ){
        ll Y=query(1, 1, N, 1, lt);
        if( (  ( ( (res*prod3)%mod  )*(prod1 ) )  )<Y  ){
            //cout<<res<<" "<<((res*prod2)%mod)<<" "<<Y<<" "<<prod<<"\n";
            res=(Y*inv(prod2))%mod;
            prod3=prod2;
            prod1=1;
            cnt++;
        }
    }
    res=(res*prod)%mod;

    return res;
}




int init(int n, int X[], int Y[]) {

    //cout<<inv(1000000000ll)<<" "<<((1000000000ll*inv(1000000000ll))%mod )<<"\n";


	N=n;
	for(int i=1; i<=N; i++){
        x[i]=X[i-1];
        y[i]=Y[i-1];
	}
    build_seg(1, 1, N);
    for(int i=1; i<=N; i++){
        prod=(prod*x[i])%mod;
    }
    for(int i=1; i<=N; i++){
        if(x[i]>1){
            suf.insert({i, x[i]});
        }
    }
	return get_resp(N);
}

int updateX(int pos, int val) {
    auto it=suf.lower_bound({pos+1, 0});
    if( (it!=suf.end()) ){
        if( (it->ft)==(pos+1) ){
            prod=(prod*inv(it->sc))%mod;
            suf.erase(it);
        }
    }
    if( (val>1) ){suf.insert({(pos+1), val});}
    prod=(prod*val)%mod;
	return get_resp(N);
}

int updateY(int pos, int val) {

    update_seg(1, 1, N, pos+1, val);

	return get_resp(N);
}

Compilation message (stderr)

horses.cpp: In function 'void update_seg(int, int, int, int, int)':
horses.cpp:52:54: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   52 | void update_seg(int v, int tl, int tr, int pos, int x){
      |                                                      ^
horses.cpp:36:5: note: shadowed declaration is here
   36 | int x[500010], y[500010];
      |     ^
horses.cpp: In function 'int get_resp(int)':
horses.cpp:86:19: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   86 | int get_resp(int N){
      |                   ^
horses.cpp:15:5: note: shadowed declaration is here
   15 | int N;
      |     ^
horses.cpp:95:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   95 |         res=query(1, 1, N, 1, lt);
      |                               ^~
horses.cpp:96:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |         return (res*prod)%mod;
      |                ~~~~~~~~~~^~~~
horses.cpp:102:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |         ll Y=query(1, 1, N, pos, lt);
      |                             ^~~
horses.cpp:102:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |         ll Y=query(1, 1, N, pos, lt);
      |                                  ^~
horses.cpp:122:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |         ll Y=query(1, 1, N, 1, lt);
      |                                ^~
horses.cpp:133:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |     return res;
      |            ^~~

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