Submission #105699

#	Time	Username	Problem	Language	Result	Execution time	Memory
105699		Pro_ktmr	역사적 조사 (JOI14_historical)	C++14	100 / 100	1916 ms	16776 KiB

historic

#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int N,Q;
vector<int> X;

vector<int> zaatu;
int change[100000];
vector<int> mp[100000];

#define B 100
#define MAX_N 100000
int si;
int co[100000];
LL bucket[MAX_N/B][MAX_N/B] = {};//i番目のブロックからj番目のブロックまで

int main(){
	scanf("%d%d", &N, &Q);
	for(int i=0; i<N; i++){ //N=10^5
		int x;
		scanf("%d", &x);
		X.push_back(x);
		zaatu.push_back(x);
	}
	for(int i=N; i%B!=0; i++){ //B
		X.push_back(0);
		zaatu.push_back(0);
	}
	sort(zaatu.begin(), zaatu.end());
	for(int i=0; i<N; i++){
		X[i] = lower_bound(zaatu.begin(), zaatu.end(), X[i]) - zaatu.begin();
		mp[X[i]].push_back(i);
	}

	si = ceil((double)N/B);
	for(int i=0; i<si; i++){ //N/B=10^3
		LL ans = 0;
		for(int j=0; j<N; j++) co[j] = 0;
		for(int j=B*i; j<si*B; j++){ //N/B=10^3
			co[X[j]]++;
			ans = max(ans, (LL)zaatu[X[j]]*(LL)co[X[j]]);
			if((j+1)%B == 0) bucket[i][(j+1)/B-1] = ans;
		}
	}

	
	for(int q=0; q<Q; q++){ //Q=10^5
		int a,b;
		scanf("%d%d", &a, &b);
		a--; b--;
		int l = ceil((double)a/B);
		int r = floor((double)b/B)-1;
		LL ans = 0;
		if(l <= r) ans = bucket[l][r];
		for(int i=a; i<l*B; i++){ //B=10^2
			LL c = upper_bound(mp[X[i]].begin(),mp[X[i]].end(),b) - lower_bound(mp[X[i]].begin(),mp[X[i]].end(),a);
			ans = max(ans, (LL)zaatu[X[i]]*c);
		}
		for(int i=(r+1)*B; i<=b; i++){ //B=10^2
			LL c = upper_bound(mp[X[i]].begin(),mp[X[i]].end(),b) - lower_bound(mp[X[i]].begin(),mp[X[i]].end(),a);
			ans = max(ans, (LL)zaatu[X[i]]*c);
		}
		cout << ans << endl;
	}

	return 0;
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:47: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:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
historic.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60