oj.uz

Submission #39541

# Submission time Handle Problem Language Result Execution time Memory
39541 2018-01-16T10:08:41 Z 14kg 역사적 조사 (JOI14_historical) C++11
100 / 100
 3329 ms 15328 KB 
#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#define N 100001
#define NN 262144
#define SQ 300
#define max2(x,y) (x>y?x:y)

using namespace std;
typedef pair<pair<int, int>, int> ppi;
int n, q_len, M_len, nn, in[N], Md[N];
long long tree[NN], out[N];
ppi Q[N];
set<int> S;
map<int, int> M;

bool cmp(ppi x, ppi y) {
	pair<int,int> tx = { x.first.first / SQ,x.first.second / SQ };
	pair<int,int> ty = { y.first.first / SQ,y.first.second / SQ };
	return tx < ty;
}
void Update(int lev) {
	tree[lev] = max2(tree[lev * 2], tree[lev * 2 + 1]);
	if (lev > 1) Update(lev / 2);
}
void Push(int x, long long num) {
	tree[nn + x - 1] += num;
	Update((nn + x - 1) / 2);
}
int main() {
	scanf("%d %d", &n, &q_len);
	for (int i = 1; i <= n; i++) scanf("%d", &in[i]), S.insert(in[i]);
	for (auto i : S) M[i] = ++M_len;
	for (int i = 1; i <= n; i++) Md[i] = M[in[i]];

	for (nn = 1; nn < M_len; nn *= 2);
	for (int i = 1; i <= q_len; i++) {
		scanf("%d %d", &Q[i].first.first, &Q[i].first.second);
		Q[i].second = i;
	}
	sort(Q + 1, Q + q_len + 1, cmp);
	
	int l = 1, r = 0;
	for (int i = 1; i <= q_len; i++) {
		int x = Q[i].first.first, y = Q[i].first.second;
		while (r < y) Push(Md[r + 1], in[r + 1]), r++;
		while (l > x) Push(Md[l - 1], in[l - 1]), l--;
		while (r > y) Push(Md[r], -in[r]), r--;
		while (l < x) Push(Md[l], -in[l]), l++;
		out[Q[i].second] = tree[1];
	}
	for (int i = 1; i <= q_len; i++) printf("%lld\n", out[i]);
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:32:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q_len);
                            ^
historic.cpp:33:67: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d", &in[i]), S.insert(in[i]);
                                                                   ^
historic.cpp:39:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &Q[i].first.first, &Q[i].first.second);
                                                        ^

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5956 KB Output is correct
2 Correct 0 ms 5956 KB Output is correct
3 Correct 3 ms 5956 KB Output is correct
4 Correct 6 ms 5956 KB Output is correct
5 Correct 19 ms 5956 KB Output is correct
6 Correct 23 ms 5956 KB Output is correct
7 Correct 29 ms 5956 KB Output is correct
8 Correct 19 ms 5956 KB Output is correct
9 Correct 19 ms 5956 KB Output is correct
10 Correct 39 ms 6088 KB Output is correct
11 Correct 36 ms 6088 KB Output is correct
12 Correct 36 ms 6088 KB Output is correct
13 Correct 39 ms 6088 KB Output is correct
14 Correct 29 ms 6088 KB Output is correct
15 Correct 33 ms 6088 KB Output is correct
16 Correct 19 ms 5956 KB Output is correct
17 Correct 9 ms 5956 KB Output is correct
18 Correct 33 ms 6088 KB Output is correct
19 Correct 33 ms 6088 KB Output is correct
20 Correct 39 ms 6220 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5956 KB Output is correct
2 Correct 0 ms 5956 KB Output is correct
3 Correct 0 ms 5956 KB Output is correct
4 Correct 0 ms 5956 KB Output is correct
5 Correct 3 ms 6088 KB Output is correct
6 Correct 0 ms 5956 KB Output is correct
7 Correct 3 ms 6088 KB Output is correct
8 Correct 6 ms 6220 KB Output is correct
9 Correct 23 ms 6616 KB Output is correct
10 Correct 9 ms 5956 KB Output is correct
11 Correct 216 ms 5956 KB Output is correct
12 Correct 36 ms 5956 KB Output is correct
13 Correct 166 ms 6616 KB Output is correct
14 Correct 473 ms 9784 KB Output is correct
15 Correct 1176 ms 11368 KB Output is correct
16 Correct 219 ms 15328 KB Output is correct
17 Correct 46 ms 5956 KB Output is correct
18 Correct 73 ms 5956 KB Output is correct
19 Correct 189 ms 15328 KB Output is correct
20 Correct 126 ms 15328 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5956 KB Output is correct
2 Correct 189 ms 6088 KB Output is correct
3 Correct 329 ms 6484 KB Output is correct
4 Correct 566 ms 7144 KB Output is correct
5 Correct 763 ms 7408 KB Output is correct
6 Correct 883 ms 6484 KB Output is correct
7 Correct 869 ms 6088 KB Output is correct
8 Correct 743 ms 5956 KB Output is correct
9 Correct 609 ms 5956 KB Output is correct
10 Correct 339 ms 5956 KB Output is correct
11 Correct 809 ms 5956 KB Output is correct
12 Correct 1249 ms 5956 KB Output is correct
13 Correct 1983 ms 6616 KB Output is correct
14 Correct 2833 ms 8992 KB Output is correct
15 Correct 3293 ms 11236 KB Output is correct
16 Correct 3329 ms 10048 KB Output is correct
17 Correct 3109 ms 9652 KB Output is correct
18 Correct 3239 ms 9388 KB Output is correct
19 Correct 3129 ms 9124 KB Output is correct
20 Correct 2863 ms 8860 KB Output is correct
21 Correct 2769 ms 8596 KB Output is correct
22 Correct 2696 ms 8464 KB Output is correct
23 Correct 2853 ms 8332 KB Output is correct
24 Correct 2776 ms 8200 KB Output is correct
25 Correct 313 ms 5956 KB Output is correct