oj.uz

Submission #164868

# Submission time Handle Problem Language Result Execution time Memory
164868 2019-11-23T19:19:24 Z CaroLinda 역사적 조사 (JOI14_historical) C++14
100 / 100
 2104 ms 257016 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
#pragma GCC optmization("O3")

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]] ;

			for(int i = l ; i <= r ; i++ )
			{
				ans = max(ans , freqTemp[a[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:13:0: warning: ignoring #pragma GCC optmization [-Wunknown-pragmas]
 #pragma GCC optmization("O3")
 
historic.cpp: In function 'int main()':
historic.cpp:43:29: warning: left operand of comma operator has no effect [-Wunused-value]
  lp(i,0,n) debug("%d " , b[i]) ;
                             ^
historic.cpp:44:14: warning: statement has no effect [-Wunused-value]
  debug("\n") ;
              ^
historic.cpp:45: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:45: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:46:14: warning: statement has no effect [-Wunused-value]
  debug("\n") ;
              ^
historic.cpp:28: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:29: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:72: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 376 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 4 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 504 KB Output is correct
5 Correct 14 ms 632 KB Output is correct
6 Correct 42 ms 632 KB Output is correct
7 Correct 20 ms 632 KB Output is correct
8 Correct 19 ms 652 KB Output is correct
9 Correct 20 ms 636 KB Output is correct
10 Correct 23 ms 888 KB Output is correct
11 Correct 58 ms 892 KB Output is correct
12 Correct 22 ms 888 KB Output is correct
13 Correct 22 ms 908 KB Output is correct
14 Correct 22 ms 888 KB Output is correct
15 Correct 22 ms 1012 KB Output is correct
16 Correct 20 ms 760 KB Output is correct
17 Correct 20 ms 760 KB Output is correct
18 Correct 22 ms 888 KB Output is correct
19 Correct 23 ms 1016 KB Output is correct
20 Correct 24 ms 1168 KB Output is correct

Subtask #3
25.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 3 ms 552 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 10 ms 2040 KB Output is correct
9 Correct 29 ms 6136 KB Output is correct
10 Correct 32 ms 2344 KB Output is correct
11 Correct 177 ms 5240 KB Output is correct
12 Correct 116 ms 5140 KB Output is correct
13 Correct 273 ms 21148 KB Output is correct
14 Correct 470 ms 106488 KB Output is correct
15 Correct 490 ms 149604 KB Output is correct
16 Correct 798 ms 257016 KB Output is correct
17 Correct 210 ms 4856 KB Output is correct
18 Correct 358 ms 6016 KB Output is correct
19 Correct 535 ms 135800 KB Output is correct
20 Correct 311 ms 134392 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1012 KB Output is correct
2 Correct 88 ms 1960 KB Output is correct
3 Correct 179 ms 6008 KB Output is correct
4 Correct 415 ms 15500 KB Output is correct
5 Correct 668 ms 23536 KB Output is correct
6 Correct 425 ms 11836 KB Output is correct
7 Correct 363 ms 5496 KB Output is correct
8 Correct 387 ms 5240 KB Output is correct
9 Correct 428 ms 5624 KB Output is correct
10 Correct 484 ms 5804 KB Output is correct
11 Correct 476 ms 5836 KB Output is correct
12 Correct 518 ms 6776 KB Output is correct
13 Correct 1321 ms 22400 KB Output is correct
14 Correct 1911 ms 86776 KB Output is correct
15 Correct 2104 ms 149180 KB Output is correct
16 Correct 2009 ms 117292 KB Output is correct
17 Correct 2037 ms 105880 KB Output is correct
18 Correct 1988 ms 96248 KB Output is correct
19 Correct 1916 ms 88204 KB Output is correct
20 Correct 1844 ms 81848 KB Output is correct
21 Correct 1864 ms 76272 KB Output is correct
22 Correct 1878 ms 72224 KB Output is correct
23 Correct 1866 ms 68728 KB Output is correct
24 Correct 1861 ms 65204 KB Output is correct
25 Correct 490 ms 5316 KB Output is correct