oj.uz

Submission #164850

# Submission time Handle Problem Language Result Execution time Memory
164850 2019-11-23T18:33:16 Z CaroLinda 역사적 조사 (JOI14_historical) C++14
5 / 100
 42 ms 976 KB 
#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] , compr[MAXN] ;
ll freqTemp[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] = p.ff ;

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

	for(int i = 0 ; i <= qtdB ; i++ )
		for(int j = i ; j <= qtdB ; j++ )
		{
			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] )
		{
			for(int i = l ; i <= r ; i++ )
				freqTemp[a[i]] += 1LL * 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]] ;
				ll help = ( b[l]+1 <= b[r]-1 ) ? freq[b[l]+1][i] - freq[b[r]][i] : 0LL ;
				if( freqTemp[a[i]] + help > ans )
					ans = freqTemp[a[i]] + help ;
			}
			for(int i = r ; i >= ini[b[r]] ; i-- )
			{
				aux.pb( a[i] ) ;
				freqTemp[a[i]] += compr[a[i]] ;
				ll help = ( b[l]+1 <= b[r]-1 ) ? freq[b[l]+1][i] - freq[b[r]][i] : 0LL ;
				if( freqTemp[a[i]] + help > ans )
					ans = freqTemp[a[i]] + help ;	
			}

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

		}

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

	}

}

Compilation message

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:70: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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 2 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Incorrect 6 ms 888 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 976 KB Output isn't correct
2 Halted 0 ms 0 KB -