제출 #1158135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158135		AlgorithmWarrior	Horses (IOI15_horses)	C++20	17 / 100	247 ms	41976 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

int const MAX=5e5+5;
int const MOD=1e9+7;

struct node{
    int prod,maxim;
};

struct AINT{
    int n;
    node v[4*MAX];
    node combine(node a,node b){
        node rasp;
        rasp.prod=1LL*a.prod*b.prod%MOD;
        rasp.maxim=max(a.maxim,b.maxim);
        return rasp;
    }
    void update(int nod,int st,int dr,int pos,int val1,int val2){
        if(st==dr){
            if(val1>-1)
                v[nod].prod=val1;
            if(val2>-1)
                v[nod].maxim=val2;
        }
        else{
            int mij=(st+dr)/2;
            if(pos<=mij)
                update(2*nod,st,mij,pos,val1,val2);
            else
                update(2*nod+1,mij+1,dr,pos,val1,val2);
            v[nod]=combine(v[2*nod],v[2*nod+1]);
        }
    }
    void init(int n,int x[],int y[]){
        this->n=n;
        int i;
        for(i=0;i<n;++i)
            update(1,0,n-1,i,x[i],y[i]);
    }
    node query(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b)
            return v[nod];
        int mij=(st+dr)/2;
        node ans={1,0};
        if(a<=mij)
            ans=combine(ans,query(2*nod,st,mij,a,b));
        if(b>mij)
            ans=combine(ans,query(2*nod+1,mij+1,dr,a,b));
        return ans;
    }
    void upd(int pos,int val1,int val2){
        update(1,0,n-1,pos,val1,val2);
    }
    node qry(int l,int r){
        return query(1,0,n-1,l,r);
    }
}aint;

set<int>interv;
int intv_max[MAX];
int x[MAX],y[MAX];

int get_best(){
    int pos=*interv.rbegin();
    long long prod=1LL*intv_max[pos]*x[pos];
    auto it=interv.rbegin();
    it=next(it);
    while(it!=interv.rend() && prod<=1e9){
        if(intv_max[*it]>prod){
            pos=*it;
            prod=intv_max[*it];
        }
        prod*=x[*it];
        it=next(it);
    }
    return 1LL*intv_max[pos]*aint.qry(0,pos).prod%MOD;
}

int init(int N, int X[], int Y[]) {
    aint.init(N,X,Y);
    int i;
    interv.insert(0);
    for(i=0;i<N;++i){
        x[i]=X[i];
        y[i]=Y[i];
        if(x[i]>1)
            interv.insert(i);
    }
    int last=N;
    for(auto it=interv.rbegin();it!=interv.rend();it=next(it)){
        intv_max[*it]=aint.qry(*it,last-1).maxim;
        last=*it;
    }
    return get_best();
}

int updateX(int pos, int val) {
	return 0;
}

int updateY(int pos, int val) {
	return 0;
}

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