Submission #59175

#	Time	Username	Problem	Language	Result	Execution time	Memory
59175		TadijaSebez	Horses (IOI15_horses)	C++11	100 / 100	477 ms	279480 KiB

horses

#include <stdio.h>
#include <set>
using namespace std;
#define mp make_pair
#define ll long long
const int mod=1e9+7;
const int N=500050;
struct SegmentTreeProduct
{
	int pro[1<<20];
	SegmentTreeProduct(){ for(int i=0;i<(1<<20);i++) pro[i]=1;}
	void Set(int i, int val){ i+=1<<19;pro[i]=val;for(i>>=1;i;i>>=1) pro[i]=(ll)pro[i<<1]*pro[i<<1|1]%mod;}
	int Get(int l, int r)
	{
		int ret=1;
		for(l+=1<<19,r+=1<<19;l<=r;l>>=1,r>>=1)
		{
			if(l%2==1) ret=(ll)ret*pro[l++]%mod;
			if(r%2==0) ret=(ll)ret*pro[r--]%mod;
		}
		return ret;
	}
} PTree;
int max(int a, int b){ return a>b?a:b;}
struct SegmentTreeMax
{
	int rmq[1<<20];
	SegmentTreeMax(){ for(int i=0;i<(1<<20);i++) rmq[i]=0;}
	void Set(int i, int val){ i+=1<<19;rmq[i]=val;for(i>>=1;i;i>>=1) rmq[i]=max(rmq[i<<1],rmq[i<<1|1]);}
	int Get(int l, int r)
	{
		int ret=0;
		for(l+=1<<19,r+=1<<19;l<=r;l>>=1,r>>=1)
		{
			if(l%2==1) ret=max(ret,rmq[l++]);
			if(r%2==0) ret=max(ret,rmq[r--]);
		}
		return ret;
	}
} MTree;
set<pair<int,int> > Set;
set<pair<int,int> >::iterator it,it1;
void Cut(int i)
{
	it=Set.lower_bound(mp(i,N));
	if(it==Set.begin()) return;
	it--;
	int l=it->first,r=it->second;
	if(r<i) return;
	if(l<i)
	{
		Set.erase(mp(l,r));
		Set.insert(mp(l,i-1));
		Set.insert(mp(i,r));
	}
}
void Split(int i){ Cut(i);Cut(i+1);}
int x[N],y[N],n;
int Solve()
{
	it=Set.end();ll p=1;int sol=(ll)PTree.Get(1,n)*y[n]%mod;
	while(it!=Set.begin())
	{
		it--;
		int b=MTree.Get(it->first,it->second);
		if(p<b) p=b,sol=(ll)PTree.Get(1,it->second)*b%mod;
		p*=x[it->first];
		if(p>mod) break;
	}
	return sol;
}
int init(int N, int X[], int Y[])
{
	int i,j;n=N;
	for(i=1;i<=n;i++) x[i]=X[i-1],y[i]=Y[i-1];
	for(i=1;i<=n;i++) PTree.Set(i,x[i]),MTree.Set(i,y[i]);
	for(i=1;i<=n;i++)
	{
		if(x[i]>1) Set.insert(mp(i,i));
		else if(x[i-1]!=1)
		{
			for(j=i+1;j<=n && x[j]==1;j++);
			Set.insert(mp(i,j-1));
		}
	}
	return Solve();
}
int updateX(int p, int v)
{
	p++;
	if(x[p]==1 && v==1) return Solve();
	if(x[p]==1) Split(p);
	if(v==1)
	{
		if(x[p-1]==1)
		{
			it=Set.lower_bound(mp(p,p));
			it1=it;it1--;
			int l=it1->first,r=it->second;
			Set.erase(it1);
			Set.erase(it);
			Set.insert(mp(l,r));
		}
		if(x[p+1]==1)
		{
			it=Set.lower_bound(mp(p,N));
			it1=it;it1--;
			int l=it1->first,r=it->second;
			Set.erase(it1);
			Set.erase(it);
			Set.insert(mp(l,r));
		}
	}
	PTree.Set(p,v);
	x[p]=v;
	return Solve();
}
int updateY(int p, int v)
{
	p++;
	MTree.Set(p,v),y[p]=v;
	return Solve();
}

Compilation message (stderr)

horses.cpp: In member function 'void SegmentTreeProduct::Set(int, int)':
horses.cpp:12:99: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  void Set(int i, int val){ i+=1<<19;pro[i]=val;for(i>>=1;i;i>>=1) pro[i]=(ll)pro[i<<1]*pro[i<<1|1]%mod;}
                                                                          ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'int SegmentTreeProduct::Get(int, int)':
horses.cpp:18:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    if(l%2==1) ret=(ll)ret*pro[l++]%mod;
                   ~~~~~~~~~~~~~~~~^~~~
horses.cpp:19:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    if(r%2==0) ret=(ll)ret*pro[r--]%mod;
                   ~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int Solve()':
horses.cpp:61:53: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  it=Set.end();ll p=1;int sol=(ll)PTree.Get(1,n)*y[n]%mod;
                              ~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:66:48: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if(p<b) p=b,sol=(ll)PTree.Get(1,it->second)*b%mod;
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:72:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[])
                                 ^
horses.cpp:7:11: note: shadowed declaration is here
 const int N=500050;
           ^

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