Submission #307288

#	Time	Username	Problem	Language	Result	Execution time	Memory
307288		vipghn2003	Horses (IOI15_horses)	C++14	34 / 100	1596 ms	22652 KiB

horses

#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int mod=1e9+7;
const int inf=1e9;
const int N=5e5+5;
int n,ST[4*N],x[N],y[N];
pii STmul[4*N];

pii mermul(pii a,pii b)
{
    if(max(a.se,b.se)==1) return mp(1ll*a.fi*b.fi%mod,1);
    pii res;
    if(1ll*a.fi*b.fi>=inf) res.se=1;
    else res.se=0;
    res.fi=1ll*a.fi*b.fi%mod;
    return res;
}

void updX(int id,int l,int r,int pos,int val)
{
    if(pos>r||pos<l) return ;
    if(l==r)
    {
        STmul[id]=mp(val,0);
        return ;
    }
    int mid=(l+r)/2;
    updX(id*2,l,mid,pos,val);
    updX(id*2+1,mid+1,r,pos,val);
    STmul[id]=mermul(STmul[id*2],STmul[id*2+1]);
}

pii get(int id,int l,int r,int u,int v)
{
    if(l>v||r<u) return mp(1,0);
    if(u<=l&&r<=v) return STmul[id];
    int mid=(l+r)/2;
    return mermul(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

int mer(int i,int j)
{
    pii mul=get(1,1,n,i+1,j);
    if(mul.se==1||1ll*mul.fi*y[j]>y[i]) return j;
    return i;
}

void upd(int id,int l,int r,int pos)
{
    if(pos>r||pos<l) return ;
    if(l==r)
    {
        ST[id]=l;
        return ;
    }
    int mid=(l+r)/2;
    upd(id*2,l,mid,pos);
    upd(id*2+1,mid+1,r,pos);
    ST[id]=mer(ST[id*2],ST[id*2+1]);
}

int init(int N,int X[],int Y[])
{
    n=N;
    for(int i=0;i<N;i++)
    {
        x[i+1]=X[i],y[i+1]=Y[i];
        updX(1,1,n,i+1,x[i+1]);
        upd(1,1,n,i+1);
    }
    int id=ST[1];
    int res=get(1,1,n,1,id).fi;
    return 1ll*res*y[id]%mod;
}

int updateX(int pos,int val)
{
    pos++;
    updX(1,1,n,pos,val);
    upd(1,1,n,pos);
    int id=ST[1];
    int res=get(1,1,n,1,id).fi;
    return 1ll*res*y[id]%mod;
}

int updateY(int pos,int val)
{
    pos++;
    y[pos]=val;
    upd(1,1,n,pos);
    int id=ST[1];
    int res=get(1,1,n,1,id).fi;
    return 1ll*res*y[id]%mod;
}
/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin>>N;
    int X[N],Y[N];
    for(int i=0;i<N;i++) cin>>X[i];
    for(int i=0;i<N;i++) cin>>Y[i];
    cout<<init(N,X,Y);
}*/

Compilation message (stderr)

horses.cpp: In function 'std::pair<int, int> mermul(std::pair<int, int>, std::pair<int, int>)':
horses.cpp:20:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 |     res.fi=1ll*a.fi*b.fi%mod;
      |            ~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:67:31: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   67 | int init(int N,int X[],int Y[])
      |                               ^
horses.cpp:10:11: note: shadowed declaration is here
   10 | const int N=5e5+5;
      |           ^
horses.cpp:78:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   78 |     return 1ll*res*y[id]%mod;
      |            ~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:88:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |     return 1ll*res*y[id]%mod;
      |            ~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:98:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |     return 1ll*res*y[id]%mod;
      |            ~~~~~~~~~~~~~^~~~

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