oj.uz

Submission #5912

# Submission time Handle Problem Language Result Execution time Memory
5912 2014-05-22T22:10:10 Z tncks0121 역사적 조사 (JOI14_historical) C++
15 / 100
 3488 ms 7060 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() {
	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
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6288 KB Output is correct
2 Correct 4 ms 6288 KB Output is correct
3 Correct 16 ms 6288 KB Output is correct
4 Correct 36 ms 6288 KB Output is correct
5 Correct 72 ms 6288 KB Output is correct
6 Correct 140 ms 6288 KB Output is correct
7 Correct 132 ms 6288 KB Output is correct
8 Correct 156 ms 6288 KB Output is correct
9 Correct 152 ms 6288 KB Output is correct
10 Correct 76 ms 6288 KB Output is correct
11 Correct 76 ms 6288 KB Output is correct
12 Correct 84 ms 6288 KB Output is correct
13 Correct 88 ms 6288 KB Output is correct
14 Correct 92 ms 6288 KB Output is correct
15 Correct 92 ms 6288 KB Output is correct
16 Correct 156 ms 6288 KB Output is correct
17 Correct 112 ms 6288 KB Output is correct
18 Correct 88 ms 6288 KB Output is correct
19 Correct 72 ms 6288 KB Output is correct
20 Correct 64 ms 6288 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6288 KB Output is correct
2 Correct 0 ms 6288 KB Output is correct
3 Correct 0 ms 6288 KB Output is correct
4 Correct 4 ms 6288 KB Output is correct
5 Correct 12 ms 6288 KB Output is correct
6 Correct 4 ms 6288 KB Output is correct
7 Correct 4 ms 6288 KB Output is correct
8 Correct 4 ms 6420 KB Output is correct
9 Correct 16 ms 6552 KB Output is correct
10 Correct 32 ms 6848 KB Output is correct
11 Runtime error 160 ms 6812 KB SIGSEGV Segmentation fault
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 6288 KB Output is correct
2 Correct 592 ms 6420 KB Output is correct
3 Correct 704 ms 6552 KB Output is correct
4 Correct 840 ms 6684 KB Output is correct
5 Correct 1060 ms 6816 KB Output is correct
6 Correct 1804 ms 6684 KB Output is correct
7 Correct 2960 ms 6684 KB Output is correct
8 Correct 3488 ms 6688 KB Output is correct
9 Correct 3140 ms 6764 KB Output is correct
10 Runtime error 96 ms 7060 KB SIGSEGV Segmentation fault
11 Halted 0 ms 0 KB -