oj.uz

Submission #36589

# Submission time Handle Problem Language Result Execution time Memory
36589 2017-12-11T13:33:57 Z IvanC 역사적 조사 (JOI14_historical) C++14
100 / 100
 1879 ms 133784 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
const int BUCKET = 327;
vector<int> ida,volta;
int freq[BUCKET][MAXN],tempfreq[MAXN],versao[MAXN],divisao[MAXN],vetor[MAXN],iteracao,N,Q;
ll precalc[BUCKET][BUCKET];
void build(int id){
	for(int i = 0;i<min((id+1)*BUCKET,N);i++){
		int j = vetor[i];
		freq[id][j]++;
	}
	memset(tempfreq,0,sizeof(tempfreq));
	ll best = 0;
	for(int i = id*BUCKET;i<N;i++){
		int j = vetor[i];
		tempfreq[j]++;
		best = max(best, 1LL*tempfreq[j]*volta[j] );
		precalc[id][divisao[i]] = best;	
	}
}
int main(){
	scanf("%d %d",&N,&Q);
	for(int i = 0;i<N;i++){
		scanf("%d",&vetor[i]);
		divisao[i] = i/BUCKET;
		ida.push_back(vetor[i]);
	}
	sort(ida.begin(),ida.end());
	ida.erase(unique(ida.begin(),ida.end()),ida.end());
	for(int i = 0;i<ida.size();i++) volta.push_back(ida[i]);
	for(int i = 0;i<N;i++){
		vetor[i] = lower_bound(ida.begin(),ida.end(),vetor[i]) - ida.begin();
	}
	int tot_baldes = (N-1)/BUCKET;
	for(int i = 0;i<=tot_baldes;i++){
		build(i);
	}
	for(int q = 1;q<=Q;q++){
		int l,r;
		scanf("%d %d",&l,&r);
		l--;r--;
		ll resp = 0;
		iteracao++;
		int l_bucket = divisao[l];
		int r_bucket = divisao[r];
		if(l_bucket == r_bucket){
			for(int i = l;i<=r;i++){
				int j = vetor[i];
				if(versao[j] != iteracao){
					versao[j] = iteracao;
					tempfreq[j] = 0;
				}
				tempfreq[j]++;
				resp = max(resp, 1LL*tempfreq[j]*volta[j] );
			}
		}
		else{
			resp = precalc[l_bucket+1][r_bucket-1];
			for(int i = l;i < (l_bucket+1)*BUCKET;i++){
				int j = vetor[i];
				if(versao[j] != iteracao){
					versao[j] = iteracao;
					tempfreq[j] = freq[r_bucket-1][j] - freq[l_bucket][j];
				}
				tempfreq[j]++;
				resp = max(resp, 1LL*tempfreq[j]*volta[j] );
			}
			for(int i = r_bucket*BUCKET;i<=r;i++){
				int j = vetor[i];
				if(versao[j] != iteracao){
					versao[j] = iteracao;
					tempfreq[j] = freq[r_bucket-1][j] - freq[l_bucket][j];
				}
				tempfreq[j]++;
				resp = max(resp, 1LL*tempfreq[j]*volta[j] );
			}
		}
		printf("%lld\n",resp);
	}
	return 0;
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<ida.size();i++) volta.push_back(ida[i]);
                 ^
historic.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&Q);
                      ^
historic.cpp:26:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&vetor[i]);
                        ^
historic.cpp:42:23: 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 0 ms 132164 KB Output is correct
2 Correct 0 ms 132164 KB Output is correct
3 Correct 0 ms 132164 KB Output is correct
4 Correct 0 ms 132164 KB Output is correct
5 Correct 0 ms 132164 KB Output is correct
6 Correct 0 ms 132164 KB Output is correct
7 Correct 0 ms 132164 KB Output is correct
8 Correct 0 ms 132164 KB Output is correct
9 Correct 0 ms 132164 KB Output is correct
10 Correct 0 ms 132164 KB Output is correct
11 Correct 0 ms 132164 KB Output is correct
12 Correct 0 ms 132164 KB Output is correct
13 Correct 0 ms 132164 KB Output is correct
14 Correct 0 ms 132164 KB Output is correct
15 Correct 0 ms 132164 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132164 KB Output is correct
2 Correct 0 ms 132164 KB Output is correct
3 Correct 0 ms 132164 KB Output is correct
4 Correct 6 ms 132164 KB Output is correct
5 Correct 13 ms 132164 KB Output is correct
6 Correct 13 ms 132304 KB Output is correct
7 Correct 16 ms 132304 KB Output is correct
8 Correct 9 ms 132304 KB Output is correct
9 Correct 9 ms 132304 KB Output is correct
10 Correct 6 ms 132304 KB Output is correct
11 Correct 16 ms 132304 KB Output is correct
12 Correct 13 ms 132304 KB Output is correct
13 Correct 9 ms 132304 KB Output is correct
14 Correct 13 ms 132304 KB Output is correct
15 Correct 13 ms 132304 KB Output is correct
16 Correct 13 ms 132304 KB Output is correct
17 Correct 9 ms 132304 KB Output is correct
18 Correct 13 ms 132304 KB Output is correct
19 Correct 13 ms 132304 KB Output is correct
20 Correct 13 ms 132304 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132164 KB Output is correct
2 Correct 0 ms 132164 KB Output is correct
3 Correct 0 ms 132164 KB Output is correct
4 Correct 0 ms 132164 KB Output is correct
5 Correct 0 ms 132164 KB Output is correct
6 Correct 0 ms 132164 KB Output is correct
7 Correct 3 ms 132304 KB Output is correct
8 Correct 9 ms 132304 KB Output is correct
9 Correct 26 ms 132436 KB Output is correct
10 Correct 39 ms 132632 KB Output is correct
11 Correct 169 ms 133016 KB Output is correct
12 Correct 96 ms 133016 KB Output is correct
13 Correct 209 ms 133016 KB Output is correct
14 Correct 393 ms 133268 KB Output is correct
15 Correct 279 ms 133268 KB Output is correct
16 Correct 426 ms 133784 KB Output is correct
17 Correct 116 ms 133016 KB Output is correct
18 Correct 186 ms 133016 KB Output is correct
19 Correct 209 ms 133784 KB Output is correct
20 Correct 133 ms 133784 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 132304 KB Output is correct
2 Correct 69 ms 132436 KB Output is correct
3 Correct 129 ms 132436 KB Output is correct
4 Correct 259 ms 132632 KB Output is correct
5 Correct 399 ms 132632 KB Output is correct
6 Correct 273 ms 132632 KB Output is correct
7 Correct 296 ms 133016 KB Output is correct
8 Correct 229 ms 133016 KB Output is correct
9 Correct 229 ms 133016 KB Output is correct
10 Correct 273 ms 133016 KB Output is correct
11 Correct 246 ms 133016 KB Output is correct
12 Correct 399 ms 133016 KB Output is correct
13 Correct 553 ms 133016 KB Output is correct
14 Correct 1489 ms 133016 KB Output is correct
15 Correct 1879 ms 133268 KB Output is correct
16 Correct 1773 ms 133268 KB Output is correct
17 Correct 1719 ms 133268 KB Output is correct
18 Correct 1616 ms 133268 KB Output is correct
19 Correct 1589 ms 133268 KB Output is correct
20 Correct 1486 ms 133016 KB Output is correct
21 Correct 1599 ms 133016 KB Output is correct
22 Correct 1426 ms 133016 KB Output is correct
23 Correct 1379 ms 133016 KB Output is correct
24 Correct 1489 ms 133016 KB Output is correct
25 Correct 349 ms 133016 KB Output is correct