oj.uz

Submission #5911

# Submission time Handle Problem Language Result Execution time Memory
5911 2014-05-22T22:10:04 Z tncks0121 역사적 조사 (JOI14_historical) C++
0 / 100
 0 ms 6280 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 100005;
const int B = 316;
int N, Q, X[N_], S[N_], SN, P[N_];
vector<int> W[N_];
ll precalc[N_/B][N_/B], C[N_];

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	scanf("%d%d", &N, &Q);
	for(int i = 0; i < N; i++) {
		scanf("%d", X+i);
		S[i] = X[i];
	}

	sort(S, S+N);
	SN = unique(S, S+N) - S;
	
	for(int i = 0; i < N; i++) {
		P[i] = lower_bound(S, S+SN, X[i]) - S;
		W[P[i]].push_back(i);
	}

	for(int i = 0; i < N; i += B) {
		for(int j = 0; j < N; j++) C[j] = 0;
		ll val = 0;
		for(int j = i; j < N; j++) {
			C[P[j]] += (ll)X[j];
			if(val < C[P[j]]) val = C[P[j]];
			if(j % B == 0) precalc[i/B][j/B] = val;
		}
	}

	while(Q--) {
		int a, b; scanf("%d%d", &a, &b); --a; --b;
		int x = a, y = b;
		ll ans = 0;
		for(; x % B != 0; ++x) {
			ll val = (ll)X[x] * (lower_bound(W[P[x]].begin(), W[P[x]].end(), b+1) - lower_bound(W[P[x]].begin(), W[P[x]].end(), a));
			if(val > ans) ans = val;
		}
		for(; y % B != 0; --y) {
			ll val = (ll)X[y] * (lower_bound(W[P[y]].begin(), W[P[y]].end(), b+1) - lower_bound(W[P[y]].begin(), W[P[y]].end(), a));
			if(val > ans) ans = val;
		}
		ans = max(ans, precalc[x/B][y/B]);

		printf("%lld\n", ans);
	}

	return 0;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 6280 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 6280 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 6280 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 6280 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -