oj.uz

Submission #164843

# Submission time Handle Problem Language Result Execution time Memory
164843 2019-11-23T18:05:14 Z CaroLinda 역사적 조사 (JOI14_historical) C++14
15 / 100
 4000 ms 77092 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] , 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

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 11 ms 764 KB Output is correct
3 Correct 21 ms 760 KB Output is correct
4 Correct 37 ms 764 KB Output is correct
5 Correct 78 ms 936 KB Output is correct
6 Correct 117 ms 1156 KB Output is correct
7 Correct 112 ms 1016 KB Output is correct
8 Correct 110 ms 968 KB Output is correct
9 Correct 116 ms 892 KB Output is correct
10 Correct 126 ms 1400 KB Output is correct
11 Correct 134 ms 1288 KB Output is correct
12 Correct 126 ms 1192 KB Output is correct
13 Correct 127 ms 1144 KB Output is correct
14 Correct 121 ms 1144 KB Output is correct
15 Correct 122 ms 1140 KB Output is correct
16 Correct 118 ms 1064 KB Output is correct
17 Correct 112 ms 1060 KB Output is correct
18 Correct 123 ms 1144 KB Output is correct
19 Correct 127 ms 1144 KB Output is correct
20 Correct 128 ms 1424 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 24 ms 888 KB Output is correct
6 Correct 8 ms 888 KB Output is correct
7 Correct 9 ms 1016 KB Output is correct
8 Correct 10 ms 1784 KB Output is correct
9 Correct 24 ms 4132 KB Output is correct
10 Correct 36 ms 2208 KB Output is correct
11 Correct 1774 ms 4300 KB Output is correct
12 Correct 92 ms 3960 KB Output is correct
13 Correct 740 ms 12228 KB Output is correct
14 Correct 3466 ms 55388 KB Output is correct
15 Execution timed out 4035 ms 77092 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 1168 KB Output is correct
2 Correct 472 ms 1724 KB Output is correct
3 Correct 959 ms 3928 KB Output is correct
4 Correct 1831 ms 8880 KB Output is correct
5 Correct 2781 ms 12920 KB Output is correct
6 Correct 1865 ms 6932 KB Output is correct
7 Correct 1656 ms 3848 KB Output is correct
8 Correct 1897 ms 3864 KB Output is correct
9 Correct 2088 ms 4364 KB Output is correct
10 Correct 2290 ms 4192 KB Output is correct
11 Correct 2265 ms 4148 KB Output is correct
12 Correct 2383 ms 4680 KB Output is correct
13 Correct 3516 ms 12608 KB Output is correct
14 Execution timed out 4021 ms 44564 KB Time limit exceeded
15 Halted 0 ms 0 KB -