Submission #1255345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255345		lambd47	Horses (IOI15_horses)	C++20	100 / 100	497 ms	40656 KiB

horses

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

#define ld long double
#define ll long long


const int mod=1e9+7;
vector<int> x,y;
int n ;
set<pair<int,int>,greater<pair<int,int>>> s;
vector<int> seg;
ll prod;

ll exp(int x,int pot){
    ll pat=x;
    ll ret=1;
    while(pot){
        if(pot%2){
            ret*=pat;
            ret%=mod;
        }
        pat*=pat;
        pat%=mod;
        pot/=2;
    }
    return ret;
}
ll inv(int x){
    return exp(x,mod-2);
}

void update(int pos, int ini, int fim, int id, int val){
    if(ini>id || fim<id)return;
    if(ini==fim){
        seg[pos]=val;return;
    }
    int e=2*pos,d=2*pos+1;
    int m=(ini+fim)/2;
    update(e,ini,m,id,val);
    update(d,m+1,fim,id,val);
    seg[pos]=max(seg[e],seg[d]);
}

int query(int pos, int ini,int fim, int l, int r){
    if(ini>r || fim<l)return 1;
    if(l<= ini && fim <= r)return seg[pos];
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    return max(query(e,ini,m,l,r),query(d,m+1,fim,l,r));

}

int calc(){
    auto pt=s.begin();
    ll prodat=1;
    int rx=1;
    int ry=1;
    ld r=1;
    while(pt!=s.end() && prodat<mod){
        auto [id,val]=(*pt);
        pt++;
        int yat=query(1,1,n,id,n);
        ld at=(ld)prodat/(ld)yat;
        if(at<r){
            r=at;
            rx=prodat;
            ry=yat;
        }
        prodat*=val;
    }
    ll resp=prod;
    resp*=ry;
    resp%=mod;
    resp*=inv(rx);
    resp%=mod;
    return resp;
}

int init(int N, int X[], int Y[]){
    n=N;
    prod=1;
    x.resize(n+1),y.resize(n+1);
    s.insert({0,1});
    seg.resize(4*n+8);
    for(int i=0;i<n;i++){
        x[i+1]=X[i];
        prod*=x[i+1];
        prod%=mod;
        y[i+1]=Y[i];
        update(1,1,n,i+1,y[i+1]);
        if(x[i+1]!=1){
            s.insert({i+1,x[i+1]});
        }
    }
    return calc();
}

int updateX(int pos, int val){
    pos++;
    if(x[pos]!=1){
        s.erase({pos,x[pos]});
        prod*=inv(x[pos]);
        prod%=mod;
    }
    x[pos]=val;
    if(x[pos]!=1){
        prod*=x[pos];
        prod%=mod;
        s.insert({pos,x[pos]});
    }
    return calc();
}
int updateY(int pos, int val){
    pos++;
    update(1,1,n,pos,val);
    return calc();
}

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