Submission #164843

#	Time	Username	Problem	Language	Result	Execution time	Memory
164843		CaroLinda	역사적 조사 (JOI14_historical)	C++14	15 / 100	4035 ms	77092 KiB

historic

#include <bits/stdc++.h>
 
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define sz size()
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define pb push_back
#define debug 
#define sq 317

const int MAXN=1e5+10 ;

using namespace std ;

int n , q , qtdB ;
int a[MAXN] , b[MAXN] , ini[MAXN] , fim[MAXN] , freqTemp[MAXN] , compr[MAXN] ;
int freq[sq][MAXN] ;
map<int,int> mapa ;

int main()
{

	scanf("%d%d", &n , &q) ;
	lp(i,0,n) scanf("%d", &a[i]) ;

	for(int i = 0 , j = 0 , k = 0 ; i < n ; i++ , j++ )
	{
		if( j == sq ) 
		{
			fim[k] = i-1 ;
			ini[++k] = i ;
			j = 0 ;
		}
		b[i] = k ;
		if( i == n-1 ) fim[k] = n-1 , qtdB = k ;
	}
	lp(i,0,n) debug("%d " , b[i]) ;
	debug("\n") ;
	lp(i,0,qtdB+1) debug("%d %d\n",ini[i] , fim[i]) ;
	debug("\n") ;

	lp(i,0,n) mapa[ a[i] ] = 0 ;
	int Key = 1 ;
	for(auto &p : mapa ) p.ss = Key ++ ;
	lp(i,0,n) a[i] = mapa[a[i]] ;
	for(auto &p : mapa ) compr[p.ss] = p.ff ;



	for(int i = 0 ; i <= qtdB ; i++ )
		for(int j = ini[i] ; j < n ; j++ )
			freq[i][ a[j] ] ++ ;

	
	while(q--)
	{
		int l , r ;
		scanf("%d%d", &l, &r ) ;
		l -- , r -- ;

		memset(freqTemp, 0, sizeof freqTemp) ;

		if( b[l]+1 <= b[r]-1 )
			lp(i,1,Key+1)
				freqTemp[i] = freq[ b[l]+1 ][i] - freq[ b[r] ][i] ;

		if( b[l] == b[r] )
		{
			for(int i = l ; i <= r ; i++ )
				freqTemp[a[i]] ++ ;
		}

		else 
		{
			for(int i = l ; i <= fim[b[l]] ; i++ )
				freqTemp[a[i]] ++ ;
			for(int i = r ; i >= ini[b[r]] ; i-- )
				freqTemp[ a[i] ] ++ ;
		}

		ll ans = 0 ;

		lp(i,1,Key+1)
			if( 1LL * compr[i] * 1LL * freqTemp[i] > ans )
				ans = 1LL * compr[i] * 1LL * freqTemp[i] ;

		printf("%lld\n" , ans ) ;

	}

}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:40:29: warning: left operand of comma operator has no effect [-Wunused-value]
  lp(i,0,n) debug("%d " , b[i]) ;
                             ^
historic.cpp:41:14: warning: statement has no effect [-Wunused-value]
  debug("\n") ;
              ^
historic.cpp:42:38: warning: left operand of comma operator has no effect [-Wunused-value]
  lp(i,0,qtdB+1) debug("%d %d\n",ini[i] , fim[i]) ;
                                      ^
historic.cpp:42:38: warning: right operand of comma operator has no effect [-Wunused-value]
  lp(i,0,qtdB+1) debug("%d %d\n",ini[i] , fim[i]) ;
                                 ~~~~~^
historic.cpp:43:14: warning: statement has no effect [-Wunused-value]
  debug("\n") ;
              ^
historic.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n , &q) ;
  ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:27:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  lp(i,0,n) scanf("%d", &a[i]) ;
            ~~~~~^~~~~~~~~~~~~
historic.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &l, &r ) ;
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60