oj.uz

Submission #164862

# Submission time Handle Problem Language Result Execution time Memory
164862 2019-11-23T19:14:55 Z CaroLinda 역사적 조사 (JOI14_historical) C++14
75 / 100
 4000 ms 149900 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] ; 
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

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.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 436 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 7 ms 508 KB Output is correct
5 Correct 14 ms 632 KB Output is correct
6 Correct 20 ms 632 KB Output is correct
7 Correct 20 ms 632 KB Output is correct
8 Correct 19 ms 632 KB Output is correct
9 Correct 20 ms 632 KB Output is correct
10 Correct 24 ms 1016 KB Output is correct
11 Correct 24 ms 888 KB Output is correct
12 Correct 25 ms 888 KB Output is correct
13 Correct 23 ms 888 KB Output is correct
14 Correct 22 ms 888 KB Output is correct
15 Correct 23 ms 888 KB Output is correct
16 Correct 20 ms 632 KB Output is correct
17 Correct 20 ms 632 KB Output is correct
18 Correct 23 ms 888 KB Output is correct
19 Correct 25 ms 1016 KB Output is correct
20 Correct 27 ms 1148 KB Output is correct

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 380 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 Correct 5 ms 760 KB Output is correct
8 Correct 11 ms 2040 KB Output is correct
9 Correct 28 ms 6264 KB Output is correct
10 Correct 32 ms 2396 KB Output is correct
11 Correct 181 ms 5240 KB Output is correct
12 Correct 117 ms 5368 KB Output is correct
13 Correct 345 ms 21368 KB Output is correct
14 Correct 2309 ms 106404 KB Output is correct
15 Execution timed out 4021 ms 149900 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 824 KB Output is correct
2 Correct 90 ms 2068 KB Output is correct
3 Correct 182 ms 6008 KB Output is correct
4 Correct 468 ms 15388 KB Output is correct
5 Correct 708 ms 23160 KB Output is correct
6 Correct 443 ms 11448 KB Output is correct
7 Correct 348 ms 5112 KB Output is correct
8 Correct 377 ms 4816 KB Output is correct
9 Correct 459 ms 5168 KB Output is correct
10 Correct 485 ms 5248 KB Output is correct
11 Correct 482 ms 5492 KB Output is correct
12 Correct 633 ms 6236 KB Output is correct
13 Correct 1340 ms 22064 KB Output is correct
14 Correct 1912 ms 86364 KB Output is correct
15 Correct 2153 ms 149716 KB Output is correct
16 Correct 2070 ms 116964 KB Output is correct
17 Correct 1966 ms 105384 KB Output is correct
18 Correct 1915 ms 96276 KB Output is correct
19 Correct 1943 ms 89104 KB Output is correct
20 Correct 1876 ms 82704 KB Output is correct
21 Correct 1990 ms 77308 KB Output is correct
22 Correct 1887 ms 72848 KB Output is correct
23 Correct 1991 ms 69320 KB Output is correct
24 Correct 1843 ms 65816 KB Output is correct
25 Correct 475 ms 5852 KB Output is correct