Submission #256977

#	Time	Username	Problem	Language	Result	Execution time	Memory
256977		eohomegrownapps	Horses (IOI15_horses)	C++14	100 / 100	489 ms	88312 KiB

horses

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

ll m = 1000000007;

ll mexp(ll a, ll b){
    if (b==0){
        return 1;
    }
    ll ans = mexp(a,b/2);
    if (b%2==0){
        return (ans*ans)%m;
    } else {
        return (((ans*ans)%m)*a)%m;
    }
}

ll minv(ll x){
    return mexp(x,m-2);
}

ll mdiv(ll a, ll b){
    //a div b mod m
    return (a*minv(b))%m;
}

//range maximum query
//4.14.20
struct Node{
    int s,e,m,v;
    Node *l, *r;
    Node(int _s, int _e, int arr[]){
        s=_s;e=_e;
        if (s==e){
            v=arr[s];
        } else {
            m=(s+e)/2;
            l=new Node(s,m,arr);
            r=new Node(m+1,e,arr);
            v=max(l->v,r->v);
        }
    }

    void update(int ind, int val){
        if (s==e){
            v=val;
            return;
        }
        if (ind<=m){
            l->update(ind,val);
        } else {
            r->update(ind,val);
        }
        v=max(l->v,r->v);
    }

    int query(int a, int b){
        if (s==a&&e==b){
            return v;
        }
        if (b<=m){
            return l->query(a,b);
        } else if (m<a){
            return r->query(a,b);
        } else {
            return max(l->query(a,m),r->query(m+1,b));
        }
    }
};
//4.11.56

Node *root;
int n;
int *xvals;
int *yvals;
set<pair<int,int>> xset;
ll xprod = 1;

int query(){
    auto it = prev(xset.end());
    ll valdiv = 1; //value 'lost' from xvals suffix

    ll maxfracn = 1;
    ll maxfracd = 1;
    
    while (true){
        if (it->first==0){break;}

        int mincrd = (it==xset.begin())?0:(prev(it)->first);
        int maxcrd = it->first-1;

        //cout<<mincrd<<' '<<maxcrd<<'\n';
        int maxy = root->query(mincrd,maxcrd);
        //cout<<maxy<<'\n';
        valdiv*=it->second;
        if (valdiv>m){
            break;
        }

        ll newfracn = maxy;
        ll newfracd = valdiv;

        if (newfracn*maxfracd>maxfracn*newfracd){
            maxfracn=newfracn;
            maxfracd=newfracd;
        }
        
        if (it==xset.begin()){break;}
        it = prev(it);
    }
    //cout<<"f "<<maxfracn<<' '<<maxfracd<<'\n';
    return (((xprod*maxfracn)%m)*minv(maxfracd))%m;
}

int init(int N, int X[], int Y[]) {
    n=N;
    root = new Node(0,n-1,Y);
    xvals=X;
    yvals=Y;
    for (int i = 0; i<n; i++){
        xprod*=xvals[i];
        xprod%=m;
        if (xvals[i]!=1){
            xset.insert({i,xvals[i]});
        }
    }
    xset.insert({n,1});
	return query();
}

int updateX(int pos, int val) {
    if (xvals[pos]!=1){
        xset.erase({pos,xvals[pos]});
    }
    xprod=mdiv(xprod,xvals[pos]);
    xvals[pos]=val;
    if (val!=1){
        xset.insert({pos,xvals[pos]});
    }
    xprod*=xvals[pos];
    xprod%=m;
	return query();
}

int updateY(int pos, int val) {
    yvals[pos]=val;
    root->update(pos,val);
	return query();
}

Compilation message (stderr)

horses.cpp: In function 'int query()':
horses.cpp:114:49: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return (((xprod*maxfracn)%m)*minv(maxfracd))%m;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

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