제출 #344989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
344989		ogibogi2004	말 (IOI15_horses)	C++14	54 / 100	1582 ms	57324 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define y1 da
#define ll long long
const ll MAXN=5e6;
const ll MOD=1e9+7;
ll x1[MAXN],y1[MAXN];
ll fastpow(ll x,ll p)
{
	if(p==0)return 1;
	ll t=fastpow(x,p/2);
	t*=t;t%=MOD;
	if(p%2==1)t*=x;
	t%=MOD;
	return t;
}
ll inverse(ll x)
{
	return fastpow(x,MOD-2);
}
set<int>notones;
int treeX[3*MAXN],treeY[3*MAXN];
void updateY(ll idx,ll l,ll r,ll q,ll val)
{
	if(l>q||r<q)return;
	if(l==r)
	{
		treeY[idx]=val;
		return;
	}
	ll mid=(l+r)/2;
	updateY(idx*2,l,mid,q,val);
	updateY(idx*2+1,mid+1,r,q,val);
	treeY[idx]=max(treeY[idx*2],treeY[idx*2+1]);
}
ll n;
ll queryY(ll idx,ll l,ll r,ll ql,ll qr)
{
	if(l>qr)return 0;
	if(r<ql)return 0;
	if(l>=ql&&r<=qr)return treeY[idx];
	ll mid=(l+r)/2;
	return max(queryY(idx*2,l,mid,ql,qr),queryY(idx*2+1,mid+1,r,ql,qr));
}

void updateX(ll idx,ll l,ll r,ll q,ll val)
{
	if(l>q||r<q)return;
	if(l==r)
	{
		treeX[idx]=val;
		treeX[idx]%=MOD;
		return;
	}
	ll mid=(l+r)/2;
	updateX(idx*2,l,mid,q,val);
	updateX(idx*2+1,mid+1,r,q,val);
	treeX[idx]=1ll*((ll)1ll*treeX[idx*2]*treeX[idx*2+1])%MOD;
}
int queryX(ll idx,ll l,ll r,ll ql,ll qr)
{
	if(l>qr)return 1;
	if(r<ql)return 1;
	if(l>=ql&&r<=qr)return treeX[idx];
	ll mid=(l+r)/2;
	return ((ll)1ll*queryX(idx*2,l,mid,ql,qr)*queryX(idx*2+1,mid+1,r,ql,qr))%MOD;
}
ll solve()
{
	if(notones.size()==0)
	{
		return queryY(1,0,n-1,0,n-1);
	}
	int last=n;
	auto it=notones.end();it--;
	ll d1=1,cnt=0,j;
	pair<ll,ll>ans;
	ans={-1,-1};
	for(;;it--)
	{
		cnt++;
		ll y1=queryY(1,0,n-1,(*it),last-1);
		if(ans.first==-1)
		{
			j=cnt;
			ans.first=y1;
			ans.second=d1;
		}
		else if(ans.first*d1<y1*ans.second)
		{
			ans.first=y1;
			ans.second=d1;
			j=cnt;
		}
		if(it==notones.begin())break;
		last=(*it);d1*=x1[(*it)];
		if(d1>(ll)1e9)break;
	}
	it=notones.end();it--;
	last=n;
	for(;;it--)
	{
		j--;
		if(j==0)
		{
			//cout<<queryX(1,0,n-1,0,(*it))<<" "<<queryY(1,0,n-1,(*it),last-1)<<endl;
			return ((ll)1ll*queryX(1,0,n-1,0,(*it))*queryY(1,0,n-1,(*it),last-1))%MOD;
		}
		last=(*it);
	}
	return 0;
}
int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0;i<N;i++)
	{
		x1[i]=X[i];
		y1[i]=Y[i];
		if(X[i]>0)
		{
			notones.insert(i);
		}
		updateX(1,0,N-1,i,X[i]);
	}
	for(int i=0;i<N;i++)
	{
		updateY(1,0,N-1,i,Y[i]);
	}
	return solve();
}

int updateX(int pos, int val) {	
	x1[pos]=val;
	if(val==1)
	{
		notones.erase(pos);
	}
	else notones.insert(pos);
	updateX(1,0,n-1,pos,x1[pos]);
	return solve();
}

int updateY(int pos, int val) {
	y1[pos]=val;
	updateY(1,0,n-1,pos,y1[pos]);
	return solve();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'void updateY(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:29:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   29 |   treeY[idx]=val;
      |              ^~~
horses.cpp: In function 'void updateX(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:52:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   52 |   treeX[idx]=val;
      |              ^~~
horses.cpp:53:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   53 |   treeX[idx]%=MOD;
      |   ~~~~~~~~~~^~~~~
horses.cpp:59:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   59 |  treeX[idx]=1ll*((ll)1ll*treeX[idx*2]*treeX[idx*2+1])%MOD;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int queryX(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:67:74: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   67 |  return ((ll)1ll*queryX(idx*2,l,mid,ql,qr)*queryX(idx*2+1,mid+1,r,ql,qr))%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:75:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |  int last=n;
      |           ^
horses.cpp:4:12: warning: declaration of 'da' shadows a global declaration [-Wshadow]
    4 | #define y1 da
      |            ^~
horses.cpp:83:6: note: in expansion of macro 'y1'
   83 |   ll y1=queryY(1,0,n-1,(*it),last-1);
      |      ^~
horses.cpp:4:12: note: shadowed declaration is here
    4 | #define y1 da
      |            ^~
horses.cpp:8:13: note: in expansion of macro 'y1'
    8 | ll x1[MAXN],y1[MAXN];
      |             ^~
horses.cpp:101:7: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |  last=n;
      |       ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:130:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  130 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:141:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  141 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:147:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  147 |  return solve();
      |         ~~~~~^~

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