Submission #414529

#	Time	Username	Problem	Language	Result	Execution time	Memory
414529		TLP39	Horses (IOI15_horses)	C++14	100 / 100	847 ms	52404 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,bool> lb;

int n;
const ll big=1000000007;
lb seg_x[2000040];
int seg_m[2000040];
ll y[500010];
int pos[500010];
int inte[2000040][2];

void build_x(int X[],int v,int st,int ed)
{
    inte[v][0]=st;
    inte[v][1]=ed;
    if(st==ed)
    {
        pos[st]=v;
        seg_x[v]={((ll)X[st])%big,((ll)X[st])>=big};
        return;
    }
    int mid=(st+ed)>>1;
    build_x(X,2*v,st,mid);
    build_x(X,2*v+1,mid+1,ed);
    ll temp=seg_x[2*v].first*seg_x[2*v+1].first;
    seg_x[v]={temp%big,(temp>=big || seg_x[2*v].second || seg_x[2*v+1].second)};
}

lb ti(lb a,lb b)
{
    ll temp=a.first*b.first;
    return {(temp%big),temp>=big || a.second || b.second};
}

lb prod(int st,int ed,int v)
{
    if(st==inte[v][0] && ed==inte[v][1]) return seg_x[v];
    int mid=(inte[v][0]+inte[v][1])>>1;
    if(ed<=mid) return prod(st,ed,2*v);
    if(st>mid) return prod(st,ed,2*v+1);
    return ti(prod(st,mid,2*v),prod(mid+1,ed,2*v+1));
}

void build_m(int v,int st,int ed)
{
    if(st==ed)
    {
        seg_m[v]=st;
        return;
    }
    int mid=(st+ed)>>1;
    build_m(2*v,st,mid);
    build_m(2*v+1,mid+1,ed);
    int a=seg_m[2*v],b=seg_m[2*v+1];
    lb temp=prod(a+1,b,1);
    if(temp.second || temp.first*y[b]>=y[a]) seg_m[v]=b;
    else seg_m[v]=a;
}

int init(int N, int X[], int Y[]) {
    n=N;
    for(int i=0;i<n;i++) y[i]=Y[i];
	build_x(X,1,0,n-1);
	build_m(1,0,n-1);
	int temp=seg_m[1];
	return (int)((prod(0,temp,1).first*y[temp])%big);
}

void change(int p)
{
    int v=pos[p];
    v>>=1;
    int a,b;
    lb temp;
    while(v)
    {
        a=seg_m[2*v];
        b=seg_m[2*v+1];
        temp=prod(a+1,b,1);
        if(temp.second || temp.first*y[b]>=y[a]) seg_m[v]=b;
        else seg_m[v]=a;
        v>>=1;
    }
}

int updateX(int p, int val) {
    int v=pos[p];
    seg_x[v]={((ll)val)%big,((ll)val)>=big};
    v>>=1;
    ll temp;
    while(v)
    {
        temp=seg_x[2*v].first*seg_x[2*v+1].first;
        seg_x[v]={temp%big,(temp>=big || seg_x[2*v].second || seg_x[2*v+1].second)};
        v>>=1;
    }
    change(p);
	int temp2=seg_m[1];
	return (int)((prod(0,temp2,1).first*y[temp2])%big);
}

int updateY(int p, int val) {
    y[p]=val;
    change(p);
	int temp2=seg_m[1];
	return (int)((prod(0,temp2,1).first*y[temp2])%big);
}

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