Submission #120172

#	Time	Username	Problem	Language	Result	Execution time	Memory
120172		dorijanlendvaj	Horses (IOI15_horses)	C++14	100 / 100	359 ms	57448 KiB

horses

#include "horses.h"
#define x first
#define y second
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int MOD=1000000007,N=500010,M=1<<19;
const char en='\n';
const ll LLINF=1ll<<60;

int n,x[N],y[N];
set<int> le;
int segP[M*2+10],segM[M*2+10];
pii v[N];

bool debug=0;

void updP(int i,int x)
{
	i+=M;
	segP[i]=x;
	for (i/=2;i;i/=2) segP[i]=segP[i*2]*1ll*segP[i*2+1]%MOD;
}

void updM(int i,int x)
{
	i+=M;
	segM[i]=x;
	for (i/=2;i;i/=2) segM[i]=max(segM[i*2],segM[i*2+1]);
}

int getP(int l,int r,int lo=0,int hi=M,int i=1)
{
	if (lo>=l && hi<=r) return segP[i];
	if (lo>=r || hi<=l) return 1;
	int mid=(lo+hi)/2;
	return getP(l,r,lo,mid,i*2)*1ll*getP(l,r,mid,hi,i*2+1)%MOD;
}

int getM(int l,int r,int lo=0,int hi=M,int i=1)
{
	if (lo>=l && hi<=r) return segM[i];
	if (lo>=r || hi<=l) return 0;
	int mid=(lo+hi)/2;
	return max(getM(l,r,lo,mid,i*2),getM(l,r,mid,hi,i*2+1));
}

#define lll __int128

int getSol()
{
	ll pro=1;
	int e,le;
	for (e=n-1;pro<=MOD-7 && e>=0;e=v[e].x) pro*=x[e],le=e;
	if (debug) cout<<"moram do "<<e<<", umnozak je "<<pro<<endl;
	lll ma=0;
	lll jedan=1;
	int f,lf;
	for (f=n-1;pro && f>=0;f=v[f].x)
	{
		ma=max(ma,pro*jedan*y[f]);
		if (debug) cout<<"na "<<f<<" je pro="<<pro<<", y="<<y[f]<<", le="<<le<<endl;
		pro/=x[f];
		if (debug) cout<<"od "<<f<<" do "<<v[f].x<<" je pro="<<pro<<", max_y="<<v[f].y<<", ma="<<(ll)(ma%MOD)<<endl;
		ma=max(ma,pro*jedan*v[f].y);
		lf=f;
	}
	return (ma%MOD)*getP(0,le)%MOD;
}

int init(int N, int X[], int Y[]) {
	n=N;
	for (int i=0;i<n;++i) x[i]=X[i],y[i]=Y[i],segP[i+M]=x[i],segM[i+M]=y[i];
	for (int i=n;i<M;++i) segP[i+M]=1;
	for (int i=M-1;i>0;--i) segP[i]=segP[i*2]*1ll*segP[i*2+1]%MOD,segM[i]=max(segM[i*2],segM[i*2+1]);
	if (debug) cout<<"pola inita gotovo"<<endl;
	for (int i=n-1;i>=0;)
	{
		le.insert(i);
		int j=i-1,ma=0;
		while (j>=0 && x[j]==1) ma=max(ma,y[j]),--j;
		v[i]={j,ma};
		if (debug) cout<<"od "<<i<<" do "<<j<<" sa maks="<<ma<<endl;
		i=j;
	}
	//if (debug) cout<<"rjesenje inita je "<<getSol()<<endl;
	return getSol();
}

int updateX(int pos, int val) {
	int sxp=x[pos];
	x[pos]=val;
	updP(pos,val);
	if (sxp==1)
	{
		if (val==1 || pos==n-1) return getSol();
		int z=*le.upper_bound(pos);
		int et=v[z].x;
		v[z]={pos,getM(pos+1,z)};
		v[pos]={et,getM(et+1,pos)};
		le.insert(pos);
		if (debug) for (int i=n-1;i>=0;i=v[i].x) cout<<"od "<<i<<" do "<<v[i].x<<" sa maks="<<v[i].y<<endl;
		return getSol();
	}
	else
	{
		if (val!=1 || pos==n-1)
		{
			return getSol();
		}
		int z=*le.upper_bound(pos);
		v[z]={v[pos].x,getM(v[pos].x+1,z)};
		v[pos]={0,0};
		le.erase(le.find(pos));
		return getSol();
	}
	return getSol();
}

int updateY(int pos, int val) {
	y[pos]=val;
	updM(pos,val);
	if (pos!=n-1)
	{
		int z=*le.upper_bound(pos);
		v[z].y=getM(v[z].x+1,z);
	}
	return getSol();
}

Compilation message (stderr)

horses.cpp: In function 'void updP(int, int)':
horses.cpp:22:22: warning: declaration of 'first' shadows a global declaration [-Wshadow]
 void updP(int i,int x)
                      ^
horses.cpp:2:11: note: shadowed declaration is here
 #define x first
           ^
horses.cpp:15:7: note: in expansion of macro 'x'
 int n,x[N],y[N];
       ^
horses.cpp:26:53: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  for (i/=2;i;i/=2) segP[i]=segP[i*2]*1ll*segP[i*2+1]%MOD;
                            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void updM(int, int)':
horses.cpp:29:22: warning: declaration of 'first' shadows a global declaration [-Wshadow]
 void updM(int i,int x)
                      ^
horses.cpp:2:11: note: shadowed declaration is here
 #define x first
           ^
horses.cpp:15:7: note: in expansion of macro 'x'
 int n,x[N],y[N];
       ^
horses.cpp: In function 'int getP(int, int, int, int, int)':
horses.cpp:41:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return getP(l,r,lo,mid,i*2)*1ll*getP(l,r,mid,hi,i*2+1)%MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int getSol()':
horses.cpp:57:8: warning: declaration of 'le' shadows a global declaration [-Wshadow]
  int e,le;
        ^~
horses.cpp:16:10: note: shadowed declaration is here
 set<int> le;
          ^~
horses.cpp:72:28: warning: conversion to 'int' from '__int128' may alter its value [-Wconversion]
  return (ma%MOD)*getP(0,le)%MOD;
         ~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:62:8: warning: variable 'lf' set but not used [-Wunused-but-set-variable]
  int f,lf;
        ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:75:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:11:26: note: shadowed declaration is here
 const int MOD=1000000007,N=500010,M=1<<19;
                          ^
horses.cpp:79:59: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  for (int i=M-1;i>0;--i) segP[i]=segP[i*2]*1ll*segP[i*2+1]%MOD,segM[i]=max(segM[i*2],segM[i*2+1]);
                                  ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int getSol()':
horses.cpp:72:22: warning: 'le' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return (ma%MOD)*getP(0,le)%MOD;
                  ~~~~^~~~~~

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