Submission #138127

#	Time	Username	Problem	Language	Result	Execution time	Memory
138127		claudy	Horses (IOI15_horses)	C++14	100 / 100	1064 ms	51320 KiB

horses

# include "horses.h"
//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;

const int mod = 1e9 + 7;

set<int>s,S;
int fen[1 << 19],x[1 << 19],y[1 << 19],t[1 << 21],n,b[1 << 19];

void upd(int nod,int l,int r,int pos,int val)
{
	if(l == r)
	{
		t[nod] = val;
		return ;
	}
	int mid = l + r >> 1;
	if(pos <= mid) upd(nod << 1,l,mid,pos,val);
	else upd(nod << 1 | 1,mid + 1,r,pos,val);
	t[nod] = max(t[nod << 1],t[nod << 1 | 1]);
}

int qry(int nod,int tl,int tr,int l,int r)
{
	if(l > r) return 0;
	if(tl == l && tr == r) return t[nod];
	int mid = tl + tr >> 1;
	return max(qry(nod << 1,tl,mid,l,min(mid,r)),qry(nod << 1 | 1,mid + 1,tr,max(mid + 1,l),r));
}

void UPD(int pos,int val)
{
	pos++;
	for(int i = pos;i <= n;i += (i & (-i)))
	{
		fen[i] *= val;
		fen[i] %= mod;
	}
}

int QRY(int pos)
{
	pos++;
	int ans = 1;
	for(int i = pos;i;i -= (i & (-i)))
	{
		ans *= fen[i];
		ans %= mod;
	}
	return ans;
}


int f()
{
	auto it = --(S.end());
	for(int i = 0;i <= 35;i++)
	{
		if(it != S.begin()) it--;
	}
	int pos = (*it) + 1;
	vector<pair<int,int>>vec;
	vector<int>hm;
	int i = pos;
	while(i < n)
	{
		if(x[i] == 1)
		{
			int r = *(S.upper_bound(i)) - 1;
			vec.pb(mp(x[i],qry(1,0,n - 1,i,r)));
			hm.pb(i);
			i = r + 1;
		}
		else
		{
			vec.pb(mp(x[i],y[i]));
			hm.pb(i);
			i++;
		}
	}
	for(int i = 0;i < sz(vec);i++) b[i] = 1;
	for(int i = 0;i < sz(vec);i++)
	{
		int j = i + 1;
		int prod = 1;
		while(j < sz(vec))
		{
			prod *= vec[j].first;
			if(prod >= vec[i].second)
			{
				b[i] = 0;
				break;
			}
			else if(prod * vec[j].second >= vec[i].second)
			{
				b[i] = 0;
			}
			else b[j] = 0;
			j++;
		}
	}
	int f = 0;
	for(int i = 0;i < sz(vec);i++)
	{
		if(b[i]) f = i;
	}
	return ((vec[f].second * QRY(hm[f])) % mod);
}

# undef int
int init(int N, int X[], int Y[])
{
# define int ll
	n = N;
	S.insert(n);S.insert(-1);
	for(int i = 0;i <= n + 1;i++) fen[i] = 1;
	for(int i = 0;i < n;i++)
	{
		x[i] = X[i];
		y[i] = Y[i];
		UPD(i,x[i]);
		if(X[i] > 1) S.insert(i);
		upd(1,0,n - 1,i,Y[i]);
	}
	//cout << f() << '\n';
	return f();
}

int pw(int val,int p)
{
	int ans = 1;
	for(int i = 0;(1LL << i) <= p;i++)
	{
		if(p & (1LL << i))
		{
			ans *= val;
			ans %= mod;
		}
		val *= val;
		val %= mod;
	}
	return ans;
}

# undef int
int updateX(int pos, int val)
{
# define int ll
	if(x[pos] > 1) S.erase(S.find(pos));
	if(val > 1) S.insert(pos);
	UPD(pos,(val * pw(x[pos],mod - 2)) % mod);
	x[pos] = val;
	//cout << f() << '\n';	
	return f();
}

# undef int
int updateY(int pos, int val)
{
# define int ll
	upd(1,0,n - 1,pos,val);
	y[pos] = val;
	//cout << f() << '\n';	
	return f();
}

Compilation message (stderr)

horses.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")
 
horses.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
horses.cpp: In function 'long long int qry(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~
horses.cpp: In function 'long long int f()':
horses.cpp:102:10: warning: declaration of 'i' shadows a previous local [-Wshadow]
  for(int i = 0;i < sz(vec);i++) b[i] = 1;
          ^
horses.cpp:85:6: note: shadowed declaration is here
  int i = pos;
      ^
horses.cpp:103:10: warning: declaration of 'i' shadows a previous local [-Wshadow]
  for(int i = 0;i < sz(vec);i++)
          ^
horses.cpp:85:6: note: shadowed declaration is here
  int i = pos;
      ^
horses.cpp:124:10: warning: declaration of 'i' shadows a previous local [-Wshadow]
  for(int i = 0;i < sz(vec);i++)
          ^
horses.cpp:85:6: note: shadowed declaration is here
  int i = pos;
      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:147:10: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return f();
         ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:175:10: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return f();
         ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:185:10: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return f();
         ~^~

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