oj.uz

Submission #164842

# Submission time Handle Problem Language Result Execution time Memory
164842 2019-11-23T17:56:35 Z ly20 역사적 조사 (JOI14_historical) C++17
100 / 100
 1536 ms 243216 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
const int sz = sqrt(MAXN) + 10;
int v[MAXN];
long long marc[MAXN];
long long mrk[sz][MAXN];
int sq[MAXN];
map <int, int> mp;
set <int> s;
set <int> :: iterator it;
int ini[sz], fim[sz];
long long rs[sz][sz];
long long IM1P2[MAXN];
int main() {
	int n, q;
	scanf("%d %d", &n, &q);
	int par = (n - 1) / sz + 1;
	for(int i = 0; i < n; i++) {
		scanf("%d", &v[i]);
		s.insert(v[i]);
	}
	int temp = 0;
	for(it = s.begin(); it != s.end(); it++) {
		mp[*it] = temp;
		IM1P2[temp] = *it;
		temp++;
	}
	//for(int i = 0; i < 10; i++) printf("%d IM1P2 = %lld\n", i, IM1P2[i]);
	for(int i = 0; i < n; i++) {
		v[i] = mp[v[i]];
		sq[i] = i / sz;
		//printf("v = %d i = %d sq = %d IM1P2 = %lld\n", v[i], i, sq[i], IM1P2[v[i]]);
	}
	for(int i = 0; i < par; i++) {
		//printf("oi\n");
		ini[i] = i * sz;
		fim[i] = min(n - 1, (i + 1) * sz - 1);
		//printf("2\n");
	}
	long long resp;
	for(int i = 0; i < par; i++) {
		resp = 0;
		for(int j = ini[i]; j < n; j++) {
			mrk[i][v[j]]++;
			//printf("%d %lld\n", v[j], IM1P2[v[j]]);
			if(mrk[i][v[j]] * IM1P2[v[j]] > resp) {
				resp = mrk[i][v[j]] * IM1P2[v[j]];
			}
			if(j == fim[sq[j]]) {
				rs[i][sq[j]] = resp;
				//printf("%d - %d : %lld\n", i, sq[j], resp);
			}
		}
	}
	for(int i = 0; i < q; i++) {
		//for(int j = 0; j < n; j++) printf("%d - %d\n", j, sq[j]);
		int a, b;
		scanf("%d %d", &a, &b); a--; b--;
		//printf("%d == %d\n%d %d\n", sq[a], sq[b], a, b);
		if(sq[a] == sq[b]) {
			//printf("%d %d\n", a + 1, b + 1);
			long long resp = 0;
			for(int j = a; j <= b; j++) {
				marc[v[j]]++;
				//printf("%lld apareceu %lld vezes\n", IM1P2[v[j]], marc[v[j]]);
				resp = max(resp, marc[v[j]] * IM1P2[v[j]]);
			}
			printf("%lld\n", resp);
			for(int j = a; j <= b; j++) marc[v[j]]--;
		}
		else {
			long long resp = 0;
			if(sq[a] != sq[b] - 1) resp = rs[sq[a] + 1][sq[b] - 1];
			for(int j = a; j <= fim[sq[a]]; j++) {
				marc[v[j]]++;
				if((marc[v[j]] + mrk[sq[a] + 1][v[j]] - mrk[sq[b]][v[j]]) * IM1P2[v[j]] > resp) {
					resp = (marc[v[j]] + mrk[sq[a] + 1][v[j]] - mrk[sq[b]][v[j]]) * IM1P2[v[j]];
				}
			}
			for(int j = b; j >= ini[sq[b]]; j--) {
				marc[v[j]]++;
				if((marc[v[j]] + mrk[sq[a] + 1][v[j]] - mrk[sq[b]][v[j]]) * IM1P2[v[j]] > resp) {
					resp = (marc[v[j]] + mrk[sq[a] + 1][v[j]] - mrk[sq[b]][v[j]]) * IM1P2[v[j]];
				}
			}
			printf("%lld\n", resp);
			for(int j = a; j <= fim[sq[a]]; j++) {
				marc[v[j]]--;
			}
			for(int j = b; j >= ini[sq[b]];j--) {
				marc[v[j]]--;
			}
		}
	}
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 12 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 11 ms 632 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 17 ms 760 KB Output is correct
8 Correct 16 ms 632 KB Output is correct
9 Correct 17 ms 632 KB Output is correct
10 Correct 28 ms 1016 KB Output is correct
11 Correct 19 ms 1016 KB Output is correct
12 Correct 18 ms 1016 KB Output is correct
13 Correct 20 ms 1016 KB Output is correct
14 Correct 18 ms 888 KB Output is correct
15 Correct 19 ms 888 KB Output is correct
16 Correct 17 ms 632 KB Output is correct
17 Correct 17 ms 760 KB Output is correct
18 Correct 17 ms 888 KB Output is correct
19 Correct 18 ms 1016 KB Output is correct
20 Correct 19 ms 1144 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 11 ms 2224 KB Output is correct
9 Correct 28 ms 6108 KB Output is correct
10 Correct 27 ms 2296 KB Output is correct
11 Correct 165 ms 5880 KB Output is correct
12 Correct 93 ms 5368 KB Output is correct
13 Correct 215 ms 20624 KB Output is correct
14 Correct 450 ms 100636 KB Output is correct
15 Correct 421 ms 141772 KB Output is correct
16 Correct 728 ms 243216 KB Output is correct
17 Correct 278 ms 4856 KB Output is correct
18 Correct 274 ms 6296 KB Output is correct
19 Correct 499 ms 130908 KB Output is correct
20 Correct 337 ms 128888 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 888 KB Output is correct
2 Correct 71 ms 2032 KB Output is correct
3 Correct 151 ms 6008 KB Output is correct
4 Correct 303 ms 15136 KB Output is correct
5 Correct 473 ms 22892 KB Output is correct
6 Correct 317 ms 11596 KB Output is correct
7 Correct 251 ms 6108 KB Output is correct
8 Correct 278 ms 5812 KB Output is correct
9 Correct 322 ms 6648 KB Output is correct
10 Correct 353 ms 6388 KB Output is correct
11 Correct 360 ms 6712 KB Output is correct
12 Correct 405 ms 7672 KB Output is correct
13 Correct 808 ms 22528 KB Output is correct
14 Correct 1414 ms 82776 KB Output is correct
15 Correct 1536 ms 141560 KB Output is correct
16 Correct 1449 ms 111480 KB Output is correct
17 Correct 1506 ms 100692 KB Output is correct
18 Correct 1448 ms 92040 KB Output is correct
19 Correct 1364 ms 85224 KB Output is correct
20 Correct 1344 ms 79108 KB Output is correct
21 Correct 1318 ms 74012 KB Output is correct
22 Correct 1303 ms 69996 KB Output is correct
23 Correct 1269 ms 66832 KB Output is correct
24 Correct 1287 ms 63320 KB Output is correct
25 Correct 451 ms 7328 KB Output is correct