Submission #1258647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258647		erering	Horses (IOI15_horses)	C++20	0 / 100	288 ms	59948 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define pb push_back
#define ll long long
const ll MOD=1e9+7,MAXN=5e5+5;
vector<ll> x,y;
multiset<int> p;
pair<int,int> seg[MAXN*4];
ll offset=1,seg2[MAXN*4];
void update(int idx,int val){
    idx+=offset;
    seg[idx]={val,idx-offset};
    idx/=2;
    while(idx>0){
        seg[idx]=max(seg[idx*2],seg[idx*2+1]);
        idx/=2;
    }
}
void update2(int idx,int val){
    idx+=offset;
    seg2[idx]=val;
    idx/=2;
    while(idx>0){
        seg2[idx]=seg2[idx*2]*seg2[idx*2+1]%MOD;
        idx/=2;
    }
}
pair<int,int> query(int node,int qlo,int qhi,int lo,int hi){
    if(lo>=qlo && hi<=qhi)return seg[node];
    if(lo>qhi || hi<qlo)return {-1,-1};
    int mid=(lo+hi)/2;
    return max(query(node*2,qlo,qhi,lo,mid),query(node*2+1,qlo,qhi,mid+1,hi));
}
ll query2(int node,int qlo,int qhi,int lo,int hi){
    if(lo>=qlo && hi<=qhi)return seg2[node];
    if(lo>qhi || hi<qlo)return 1;
    int mid=(lo+hi)/2;
    return query2(node*2,qlo,qhi,lo,mid)*query2(node*2+1,qlo,qhi,mid+1,hi)%MOD;
}
ll pref[MAXN];
bool cmp(pair<int,int> p1,pair<int,int> p2){
    if(p1.first>p2.first)swap(p1,p2);
    if(pref[p2.first]/pref[p1.first]>y[p1.first])return 1;
    ll mult=pref[p2.first]/pref[p1.first]*y[p2.first];
    return mult>y[p1.first];
}
ll sol(){
    ll last=y.size()-1;
    auto it=p.end();
    vector<pair<ll,ll>> vec;
    ll mult=1;
    for(int i=0;i<min(31,(int)p.size());i++){
        it--;
        int id=*it;
        if(last>id)vec.pb(query(1,id+1,last,0,offset-1));
        vec.pb({y[id],id});
        mult*=x[id];
        if(mult>=(long long)1e9){
            last=-1;
            break;
        }
        last=id-1;
    }
    if(p.size()<31 && last>=0)vec.pb(query(1,0,last,0,offset-1));
    for(int i=0;i<vec.size();i++)swap(vec[i].first,vec[i].second);
    sort(vec.begin(),vec.end());
    pref[vec[0].first]=x[vec[0].first];
    for(int i=1;i<vec.size();i++)pref[vec[i].first]=x[vec[i].first]*pref[vec[i-1].first];
    int best=vec.size()-1;
    for(int i=vec.size()-2;i>=0;i--){
        if(cmp(vec[i],vec[best]))best=i;
    }
   // cout<<best<<' '<<vec[best].first<<endl;
    ll ans=query2(1,0,vec[best].first,0,offset-1);
    ans*=vec[best].second; ans%=MOD;
    return ans;
}
int init(int N, int X[], int Y[]) {
    for(int i=0;i<MAXN*4;i++)seg2[i]=1;
    while(offset<N)offset*=2;
    for(int i=0;i<N;i++){
        x.pb(X[i]); y.pb(Y[i]);
        update(i,Y[i]);
        update2(i,X[i]);
        if(X[i]!=1)p.insert(i);
    }
    return (int)sol();
}

int updateX(int pos, int val) {
    if(x[pos]==1 && val!=1)p.insert(pos);
    if(x[pos]!=1 && val==1)p.erase(pos);
    x[pos]=val;
    update2(pos,x[pos]);
    return (int)sol();
}

int updateY(int pos, int val) {
    y[pos]=val;
    update(pos,val);
    return (int)sol();
}

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