제출 #121658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121658		CaroLinda	말 (IOI15_horses)	C++14	17 / 100	1558 ms	37944 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"

#define ll long long
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int MOD = 1e9+7 ;
const int MAXN=5e5+10;

using namespace std ;

// ------------x------------

struct segOfMaximum
{
	int v[MAXN*4];
	int m(int l, int r){ return (l+r)/2 ; }
	
	void upd(int pos, int l, int r, int x, int val)
	{
		if(l==r) { v[pos] = val; return ; }
		if(x<=m(l,r)) upd(pos*2,l,m(l,r),x,val) ;
		else upd(pos*2+1,m(l,r)+1, r, x, val) ;
		v[pos] =max(v[pos*2], v[pos*2+1]);
	}
	
	int query(int pos, int l, int r, int beg, int en)
	{
		if(l>en || r<beg)return -1;
		if(l>=beg && r<=en) return v[pos];
		int rl = query(pos*2, l, m(l,r),beg,en) ;
		int rr = query(pos*2+1,m(l,r)+1, r, beg, en) ;
		return max(rl,rr) ; 
	}
	
	void print(int pos, int l, int r)
	{
		printf("%d %d -> %d\n" , l ,r,v[pos]) ;
		if(l==r)return ;
		print(pos*2,l,m(l,r)) ;
		print(pos*2+1, m(l,r)+1, r) ;
	}
	
} ;

// ------------x------------
int n , x[MAXN] , y[MAXN] ;
set<pii> s ;
segOfMaximum cuteSeg ;

ll intervalFun(vector<pii> &v)
{
	
	ll acumProd = 1 ;
	ll myAns = 0 ;
	
	int i = 0 , j = v.size()  ;
	
	for(int g = 1 ; g < j ; g++ )
	{
		acumProd *= v[g].ff ;
		if(acumProd >= 1000000000) 
			acumProd/=v[++i].ff ;
	}
	
	acumProd=1 ;
	
	for(int g = i; g < j ; g++ )
	{
		acumProd *= v[g].ff ;
		myAns = max(myAns, acumProd*v[g].ss ) ;
	}
	
	lp(g,0,i) myAns = (myAns * v[g].ff)%MOD ;
	
	return myAns ;
	
}

int ans()
{
	
	int cont = 0  ;
	set<pii>::iterator it= s.end() , it2 ;
	
	while(cont<30 && it!=s.begin())
	{
		--it ;
		if(it->ff == it->ss && x[it->ss]>1)
			cont ++ ;
	}
	
	vector<pii> myVector ;
	
	it2= it ;
	
	while(it!=s.end())
	{
		myVector.pb( mk( x[it->ff] ,cuteSeg.query(1,0,n-1,it->ff, it->ss) ) ) ;
		++it;
	}
	
	ll cool= intervalFun(myVector) ;
	
	while(it2 != s.begin())
	{
		--it2 ;
		cool *= x[it2->ff] ;
		cool %= MOD;
	}
	
	return cool ;
	
}

int init(int N, int X[] ,int Y[])
{
	n = N ;
	lp(i,0,n) x[i] = X[i] , y[i]= Y[i] ;
	
	lp(i,0,n)
	{
		int j = i ;
		while(j<n && x[j] == 1 ) {j++;}
		if(x[i] ==1) j-- ;
		s.insert(mk(i,j)) ;
		i = j ;
	}
	
	lp(i,0,n) cuteSeg.upd(1,0,n-1,i,y[i]) ;
	
	return ans() ;
	
}

int updateY(int pos, int val)
{
	cuteSeg.upd(1,0,n-1, pos,val) ;
	return ans() ;
}

int updateX(int pos, int val)
{
	set<pii>::iterator it ;
	if(x[pos] > 1 && val == 1)
	{
		it = s.find(mk(pos,pos)) ;
		int beg = pos , en = pos ;
		
		if(it!=s.begin()) beg = (--it)->ff , ++it;
		if(it!=s.end()) en = (++it)->ss , --it;
		
		if(x[beg]>1) beg=pos ;
		if(x[en]>1) en = pos ;
		
		s.erase(it) ;
		s.insert(mk(beg,en)) ;
		
	}
	
	else if(x[pos] == 1 && val > 1)
	{
		it= s.upper_bound( mk(pos,MOD) ) ;
		--it;
		int beg = it->ff , en = it->ss ;
		s.erase(it) ;
		
		if( pos != beg )
			s.insert( mk( beg , pos-1 ) ) ;
		if( pos != en )
			s.insert(mk( pos+1, en )) ;
		s.insert(mk(pos,pos)) ;
	} 
	
	x[pos] = val ;
	
	return ans() ;
	
}

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

horses.cpp: In function 'long long int intervalFun(std::vector<std::pair<int, int> >&)':
horses.cpp:62:24: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int i = 0 , j = v.size()  ;
                  ~~~~~~^~
horses.cpp: In function 'int ans()':
horses.cpp:117:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return cool ;
         ^~~~

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