oj.uz

Submission #42321

# Submission time Handle Problem Language Result Execution time Memory
42321 2018-02-26T03:15:03 Z minkank 역사적 조사 (JOI14_historical) C++14
100 / 100
 249 ms 66044 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

#define st first
#define nd second
typedef pair<int, int> ii;

ii qu[N];
int n, m, a[N], Time, b[N];
long long ans[N];
vector<int> Q[N];
map<int, int> sax;
int cnt[N], cnt2[N];

bool cmp(int a, int b) { return qu[a].nd < qu[b].nd; }

signed main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		if(!sax[a[i]]) sax[a[i]] = ++Time;
		b[i] = sax[a[i]];
	}
	for(int i = 1; i <= m; ++i)
		cin >> qu[i].st >> qu[i].nd, Q[(long long)(qu[i].st / sqrt(n))].push_back(i);
	for(int i = 0; i <= sqrt(n); ++i) {
		sort(Q[i].begin(), Q[i].end(), cmp);
		int maxL = 0;
		for(int j = 0; j < Q[i].size(); ++j) maxL = max(maxL, qu[Q[i][j]].st);
		int cur = maxL;
		long long curmx = 0;
		memset(cnt, 0, sizeof cnt);
		for(int j = 0; j < Q[i].size(); ++j) {
			int id = Q[i][j], L = qu[id].st, R = qu[id].nd;
			while(cur <= R) {
				int x = a[cur];
				cnt[b[cur]]++; curmx = max(curmx, 1LL * cnt[b[cur]] * x);
				cur++;
			}
			ans[id] = curmx;
			for(int k = L; k < min(maxL, R + 1); ++k) {
				int x = a[k];
				cnt2[b[k]]++; ans[id] = max(ans[id], 1LL * (cnt2[b[k]] + cnt[b[k]]) * x);
			}
			for(int k = L; k < min(maxL, R + 1); ++k) {
				int x = a[k];
				cnt2[b[k]]--;
			}
		}
	}
	for(int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < Q[i].size(); ++j) maxL = max(maxL, qu[Q[i][j]].st);
                    ^
historic.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < Q[i].size(); ++j) {
                    ^
historic.cpp:49:9: warning: unused variable 'x' [-Wunused-variable]
     int x = a[k];
         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 4 ms 3172 KB Output is correct
3 Correct 4 ms 3280 KB Output is correct
4 Correct 4 ms 3280 KB Output is correct
5 Correct 4 ms 3280 KB Output is correct
6 Correct 4 ms 3284 KB Output is correct
7 Correct 5 ms 3416 KB Output is correct
8 Correct 4 ms 3416 KB Output is correct
9 Correct 5 ms 3416 KB Output is correct
10 Correct 4 ms 3416 KB Output is correct
11 Correct 4 ms 3416 KB Output is correct
12 Correct 4 ms 3416 KB Output is correct
13 Correct 4 ms 3416 KB Output is correct
14 Correct 5 ms 3420 KB Output is correct
15 Correct 4 ms 3424 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3560 KB Output is correct
2 Correct 4 ms 3560 KB Output is correct
3 Correct 5 ms 3608 KB Output is correct
4 Correct 5 ms 3640 KB Output is correct
5 Correct 8 ms 3844 KB Output is correct
6 Correct 9 ms 3880 KB Output is correct
7 Correct 9 ms 3952 KB Output is correct
8 Correct 8 ms 4036 KB Output is correct
9 Correct 8 ms 4100 KB Output is correct
10 Correct 9 ms 4292 KB Output is correct
11 Correct 14 ms 4416 KB Output is correct
12 Correct 10 ms 4448 KB Output is correct
13 Correct 10 ms 4668 KB Output is correct
14 Correct 9 ms 4668 KB Output is correct
15 Correct 15 ms 4732 KB Output is correct
16 Correct 9 ms 4828 KB Output is correct
17 Correct 8 ms 4924 KB Output is correct
18 Correct 9 ms 5020 KB Output is correct
19 Correct 10 ms 5120 KB Output is correct
20 Correct 10 ms 5212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5212 KB Output is correct
2 Correct 4 ms 5212 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 4 ms 5212 KB Output is correct
5 Correct 6 ms 5212 KB Output is correct
6 Correct 5 ms 5212 KB Output is correct
7 Correct 7 ms 5256 KB Output is correct
8 Correct 11 ms 5444 KB Output is correct
9 Correct 21 ms 6080 KB Output is correct
10 Correct 14 ms 6212 KB Output is correct
11 Correct 85 ms 10556 KB Output is correct
12 Correct 30 ms 10556 KB Output is correct
13 Correct 63 ms 11020 KB Output is correct
14 Correct 107 ms 15168 KB Output is correct
15 Correct 132 ms 19736 KB Output is correct
16 Correct 177 ms 21672 KB Output is correct
17 Correct 60 ms 21672 KB Output is correct
18 Correct 107 ms 21672 KB Output is correct
19 Correct 150 ms 27028 KB Output is correct
20 Correct 119 ms 27028 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27028 KB Output is correct
2 Correct 26 ms 27028 KB Output is correct
3 Correct 65 ms 27028 KB Output is correct
4 Correct 69 ms 27028 KB Output is correct
5 Correct 92 ms 27028 KB Output is correct
6 Correct 109 ms 27028 KB Output is correct
7 Correct 109 ms 28020 KB Output is correct
8 Correct 121 ms 30284 KB Output is correct
9 Correct 137 ms 32624 KB Output is correct
10 Correct 194 ms 34396 KB Output is correct
11 Correct 173 ms 36312 KB Output is correct
12 Correct 160 ms 38272 KB Output is correct
13 Correct 173 ms 40560 KB Output is correct
14 Correct 214 ms 44020 KB Output is correct
15 Correct 226 ms 47516 KB Output is correct
16 Correct 217 ms 48888 KB Output is correct
17 Correct 206 ms 50760 KB Output is correct
18 Correct 239 ms 52732 KB Output is correct
19 Correct 249 ms 54852 KB Output is correct
20 Correct 225 ms 56764 KB Output is correct
21 Correct 222 ms 58848 KB Output is correct
22 Correct 196 ms 60776 KB Output is correct
23 Correct 199 ms 62840 KB Output is correct
24 Correct 197 ms 64832 KB Output is correct
25 Correct 212 ms 66044 KB Output is correct