Submission #164862

#	Time	Username	Problem	Language	Result	Execution time	Memory
164862		CaroLinda	역사적 조사 (JOI14_historical)	C++14	75 / 100	4021 ms	149900 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] ; 
ll freqTemp[MAXN] , compr[MAXN] ;
ll resp[sq][sq] ,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] = 1LL * p.ff ;

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

	for(int i = 0 ; i <= qtdB ; i++ )
		for(int j = i ; j <= qtdB ; j++ )
		{
			if( j-1 >= 0 )
				resp[i][j] = resp[i][j-1] ;

			for(int k = ini[j] ; k <= fim[j] ; k++ )
				resp[i][j] = max( resp[i][j] , freq[i][ a[k] ] - freq[j+1][ a[k] ] ) ;
		}

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

		ll ans = 0LL ;

		if( b[l] == b[r] || b[l] == b[r]-1 )
		{
			for(int i = l ; i <= r ; i++ )
				freqTemp[a[i]] += compr[a[i]] ;
			ans = *max_element(freqTemp, freqTemp + Key) ;
			for(int i = l ; i <= r ; i++ )
				freqTemp[a[i]] = 0LL ;
		}
		else
		{
			ans = resp[ b[l]+1 ][ b[r]-1 ] ;

			vector<int> aux ;

			for(int i = l ; i <= fim[b[l]] ; i++ )
			{
				aux.pb( a[i] ) ;
				freqTemp[a[i]] += compr[a[i]] ;
				if( freqTemp[a[i]] + freq[b[l]+1][a[i]] - freq[b[r]][a[i]] > ans )
					ans = freqTemp[a[i]] + freq[b[l]+1][a[i]] - freq[b[r]][a[i]] ;
			}
			for(int i = r ; i >= ini[b[r]] ; i-- )
			{
				aux.pb( a[i] ) ;
				freqTemp[a[i]] += compr[a[i]] ;
				if( freqTemp[a[i]] + freq[b[l]+1][a[i]] - freq[b[r]][a[i]] > ans )
					ans = freqTemp[a[i]] + freq[b[l]+1][a[i]] - freq[b[r]][a[i]] ;
			}

			for(int i : aux ) freqTemp[i] = 0LL ;

		}

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

	}

}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:42:29: warning: left operand of comma operator has no effect [-Wunused-value]
  lp(i,0,n) debug("%d " , b[i]) ;
                             ^
historic.cpp:43:14: warning: statement has no effect [-Wunused-value]
  debug("\n") ;
              ^
historic.cpp:44:40: 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:44:40: 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:45:14: warning: statement has no effect [-Wunused-value]
  debug("\n") ;
              ^
historic.cpp:27: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:28: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:71: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: 60 / 60