Submission #568606

#	Time	Username	Problem	Language	Result	Execution time	Memory
568606		n0sk1ll	Horses (IOI15_horses)	C++14	100 / 100	767 ms	56688 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>

#define xx first
#define yy second
#define ff(i,a,b) for (int i=a;i<b;i++)
#define fff(i,a,b) for (int i=a;i<=b;i++)
#define bff(i,a,b) for (int i=b-1;i>=a;i--)
#define bfff(i,a,b) for (int i=b;i>=a;i--)

using namespace std;
long long int typedef li;
const int mod=1000000007;

set<int> veci2;

int k=1,n;
int mx[1111111],val[1111111];
int l[1111111],r[1111111];

int Pro(int p, int ll, int rr)
{
    if (ll>r[p] || rr<l[p]) return 1;
    if (ll<=l[p] && rr>=r[p]) return val[p];
    return (li)Pro(2*p,ll,rr)*Pro(2*p+1,ll,rr)%mod;
}

int Max(int p, int ll, int rr)
{
    if (ll>r[p] || rr<l[p]) return 0;
    if (ll<=l[p] && rr>=r[p]) return mx[p];
    return max(Max(2*p,ll,rr),Max(2*p+1,ll,rr));
}

int opti_mala()
{
    if (veci2.empty()) return Max(1,0,n-1);
    auto it=veci2.end();
    li tmp=1;
    vector<int> salim_se1;
    vector<int> salim_se2;
    vector<int> salim_se_ind;
    while (true)
    {
        --it;

        salim_se1.push_back(tmp);
        salim_se2.push_back(Max(1,*it,n-1));
        salim_se_ind.push_back(*it);

        tmp*=val[*it+k];
        if (tmp>mod) break;
        if (it==veci2.begin()) break;
    }

    reverse(salim_se1.begin(),salim_se1.end());
    reverse(salim_se2.begin(),salim_se2.end());
    reverse(salim_se_ind.begin(),salim_se_ind.end());

    int opt=0;
    ff(i,1,salim_se1.size()) if ((li)salim_se1[opt]*salim_se2[i]>(li)salim_se1[i]*salim_se2[opt]) opt=i;
    //cout<<"opt: "<<salim_se_ind[opt]<<endl;
    return (li)salim_se2[opt]*Pro(1,0,salim_se_ind[opt])%mod;
}

int init(int N, int X[], int Y[])
{
    n=N;
    while (k<n) k*=2;
    ff(i,0,k) l[i+k]=i,r[i+k]=i;
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
    ff(i,0,n) mx[i+k]=Y[i],val[i+k]=X[i];
    bff(i,1,k) mx[i]=max(mx[2*i],mx[2*i+1]);
    bff(i,1,k) val[i]=(li)val[2*i]*val[2*i+1]%mod;

    ff(i,0,n) if (X[i]>1) veci2.insert(i);
    veci2.insert(0);
    //ff(i,0,n) veci2.insert(i);

	return opti_mala();
}

int updateX(int p, int x)
{
	p+=k;
	if (x<=1 && p) veci2.erase(p-k);
	else veci2.insert(p-k);
	val[p]=x,p>>=1;

	while (p)
    {
        val[p]=(li)val[2*p]*val[2*p+1]%mod;
        p>>=1;
    }
	return opti_mala();
}

int updateY(int p, int x)
{
	p+=k,mx[p]=x,p>>=1;
	while (p)
    {
        mx[p]=max(mx[2*p],mx[2*p+1]);
        p>>=1;
    }
	return opti_mala();
}

/*

3
2 1 3
3 4 1
1
2 1 2

*/

Compilation message (stderr)

horses.cpp: In function 'int Pro(int, int, int)':
horses.cpp:26:47: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   26 |     return (li)Pro(2*p,ll,rr)*Pro(2*p+1,ll,rr)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int opti_mala()':
horses.cpp:48:29: warning: conversion from 'li' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   48 |         salim_se1.push_back(tmp);
      |                             ^~~
horses.cpp:7:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define ff(i,a,b) for (int i=a;i<b;i++)
......
   62 |     ff(i,1,salim_se1.size()) if ((li)salim_se1[opt]*salim_se2[i]>(li)salim_se1[i]*salim_se2[opt]) opt=i;
      |        ~~~~~~~~~~~~~~~~~~~~      
horses.cpp:62:5: note: in expansion of macro 'ff'
   62 |     ff(i,1,salim_se1.size()) if ((li)salim_se1[opt]*salim_se2[i]>(li)salim_se1[i]*salim_se2[opt]) opt=i;
      |     ^~
horses.cpp:64:57: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   64 |     return (li)salim_se2[opt]*Pro(1,0,salim_se_ind[opt])%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:75:46: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   75 |     bff(i,1,k) val[i]=(li)val[2*i]*val[2*i+1]%mod;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:93:39: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   93 |         val[p]=(li)val[2*p]*val[2*p+1]%mod;
      |                ~~~~~~~~~~~~~~~~~~~~~~~^~~~

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