Submission #443743

#	Time	Username	Problem	Language	Result	Execution time	Memory
443743		jk410	Horses (IOI15_horses)	C++17	100 / 100	1263 ms	44088 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const ll MX=1e9,MX_N=5e5,MOD=1e9+7;
const ll SZ=(1<<(int)ceil(log2(MX_N))+1);
int N;
ll X[MX_N+1],Y[MX_N+1],XTree[SZ],YTree[SZ];
priority_queue<int> Q;
vector<int> Idx;
ll mul_update(ll *tree,int s,int e,int idx,ll v,int n){
    if (idx<s||e<idx)
        return tree[n];
    if (s==e)
        return tree[n]=v;
    int m=(s+e)>>1;
    return tree[n]=mul_update(tree,s,m,idx,v,n<<1)*mul_update(tree,m+1,e,idx,v,n<<1|1)%MOD;
}
ll mul_query(ll *tree,int s,int e,int l,int r,int n){
    if (r<s||e<l)
        return 1;
    if (l<=s&&e<=r)
        return tree[n];
    int m=(s+e)>>1;
    return mul_query(tree,s,m,l,r,n<<1)*mul_query(tree,m+1,e,l,r,n<<1|1)%MOD;
}
ll max_update(ll *tree,int s,int e,int idx,ll v,int n){
    if (idx<s||e<idx)
        return tree[n];
    if (s==e)
        return tree[n]=v;
    int m=(s+e)>>1;
    return tree[n]=max(max_update(tree,s,m,idx,v,n<<1),max_update(tree,m+1,e,idx,v,n<<1|1));
}
ll max_query(ll *tree,int s,int e,int l,int r,int n){
    if (r<s||e<l)
        return 0;
    if (l<=s&&e<=r)
        return tree[n];
    int m=(s+e)>>1;
    return max(max_query(tree,s,m,l,r,n<<1),max_query(tree,m+1,e,l,r,n<<1|1));
}
int ans(){
    Idx.clear();
    Idx.push_back(N);
    ll mul=1;
    while (!Q.empty()){
        int t=Q.top();
        Q.pop();
        Idx.push_back(t);
        mul*=X[t];
        if (mul>MX)
            break;
    }
    if (mul<=MX)
        Idx.push_back(0);
    mul=1;
    ll max_x=X[Idx.back()],max_y=0;
    int idx;
    for (int i=Idx.size()-1; i>0; i--){
        mul*=X[Idx[i]];
        ll t=max_query(YTree,0,N-1,Idx[i],Idx[i-1]-1,1);
        if (max_y<mul/max_x*t){
            max_x=mul;
            max_y=t;
            idx=Idx[i-1]-1;
        }
    }
    for (int i:Idx){
        if (X[i]>1)
            Q.push(i);
    }
    return mul_query(XTree,0,N-1,0,idx,1)*max_y%MOD;
}
int init(int n, int x[], int y[]){
    N=n;
    for (int i=0; i<N; i++){
        X[i]=x[i];
        if (X[i]>1)
            Q.push(i);
        mul_update(XTree,0,N-1,i,X[i],1);
        Y[i]=y[i];
        max_update(YTree,0,N-1,i,Y[i],1);
    }
	return ans();
}

int updateX(int pos, int val) {
    if (val>1&&X[pos]==1)
        Q.push(pos);
    X[pos]=val;
    mul_update(XTree,0,N-1,pos,val,1);
	return ans();
}

int updateY(int pos, int val) {
    Y[pos]=val;
    max_update(YTree,0,N-1,pos,val,1);
	return ans();
}

Compilation message (stderr)

horses.cpp:6:38: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    6 | const ll SZ=(1<<(int)ceil(log2(MX_N))+1);
      |                 ~~~~~~~~~~~~~~~~~~~~~^~
horses.cpp: In function 'int ans()':
horses.cpp:60:26: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   60 |     for (int i=Idx.size()-1; i>0; i--){
      |                ~~~~~~~~~~^~
horses.cpp:73:48: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   73 |     return mul_query(XTree,0,N-1,0,idx,1)*max_y%MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:73:21: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     return mul_query(XTree,0,N-1,0,idx,1)*max_y%MOD;
      |            ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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