oj.uz

Submission #259604

# Submission time Handle Problem Language Result Execution time Memory
259604 2020-08-08T03:59:46 Z 송준혁(#5058) 역사적 조사 (JOI14_historical) C++17
40 / 100
 4000 ms 36464 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mup(a,x) a=max(a, x)
#define mup(a,x) a=min(a, x)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define INF (1ll<<60)
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;

int N, Q, B=300;
LL A[101010], M[101010], ans[101010];
vector<LL> comp;
priority_queue<pii> S;

struct query{
	int s, e, id;
} P[101010];

int main(){
	scanf("%d %d", &N, &Q);
	for (int i=1; i<=N; i++){
		scanf("%lld", &A[i]);
		comp.pb(A[i]);
	}
	for (int i=1; i<=Q; i++) scanf("%d %d", &P[i].s, &P[i].e), P[i].id=i;
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	for (int i=1; i<=N; i++) A[i] = lower_bound(comp.begin(), comp.end(), A[i])-comp.begin();
	sort(P+1, P+Q+1, [&](query a, query b){
		if (a.s/B == b.s/B) {
			if ((a.s/B)&1) return a.e > b.e;
			return a.e < a.e;
		}
		return a.s < b.s;
	});
	int l=1, r=1;
	M[A[1]] = comp[A[1]];
	S.push(pii(comp[A[1]], A[1]));
	for (int i=1; i<=Q; i++){
		for (int j=r+1; j<=P[i].e; j++){
			M[A[j]] += comp[A[j]];
			S.push(pii(M[A[j]], A[j]));
		}
		for (int j=P[i].s; j<l; j++) {
			M[A[j]] += comp[A[j]];
			S.push(pii(M[A[j]], A[j]));
		}
		for (int j=P[i].e+1; j<=r; j++) {
			M[A[j]] -= comp[A[j]];
			if (M[A[j]]) S.push(pii(M[A[j]], A[j]));
		}
		for (int j=l; j<P[i].s; j++) {
			M[A[j]] -= comp[A[j]];
			if (M[A[j]]) S.push(pii(M[A[j]], A[j]));
		}
		while (M[S.top().se] != S.top().fi) S.pop();
		ans[P[i].id] = S.top().fi;
		l=P[i].s, r=P[i].e;
	}
	for (int i=1; i<=Q; i++) printf("%lld\n", ans[i]);
	return 0;
}

Compilation message

historic.cpp: In lambda function:
historic.cpp:36:15: warning: self-comparison always evaluates to false [-Wtautological-compare]
    return a.e < a.e;
           ~~~~^~~~~
historic.cpp: In function 'int main()':
historic.cpp:24: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:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &A[i]);
   ~~~~~^~~~~~~~~~~~~~~
historic.cpp:29:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=Q; i++) scanf("%d %d", &P[i].s, &P[i].e), P[i].id=i;
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Correct 9 ms 1020 KB Output is correct
18 Correct 25 ms 1528 KB Output is correct
19 Correct 75 ms 2536 KB Output is correct
20 Correct 267 ms 4708 KB Output is correct
21 Correct 602 ms 4708 KB Output is correct
22 Correct 586 ms 8924 KB Output is correct
23 Correct 543 ms 2664 KB Output is correct
24 Correct 590 ms 4708 KB Output is correct
25 Correct 478 ms 33516 KB Output is correct
26 Correct 483 ms 17280 KB Output is correct
27 Correct 512 ms 17104 KB Output is correct
28 Correct 437 ms 33596 KB Output is correct
29 Correct 545 ms 33432 KB Output is correct
30 Correct 528 ms 17104 KB Output is correct
31 Correct 557 ms 2668 KB Output is correct
32 Correct 409 ms 1148 KB Output is correct
33 Correct 529 ms 17232 KB Output is correct
34 Correct 560 ms 33468 KB Output is correct
35 Correct 385 ms 33488 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 12 ms 1528 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 1148 KB Output is correct
8 Correct 6 ms 1148 KB Output is correct
9 Correct 12 ms 1912 KB Output is correct
10 Correct 26 ms 1400 KB Output is correct
11 Correct 1633 ms 36464 KB Output is correct
12 Correct 52 ms 4072 KB Output is correct
13 Correct 388 ms 35256 KB Output is correct
14 Correct 768 ms 36164 KB Output is correct
15 Correct 705 ms 5480 KB Output is correct
16 Correct 111 ms 11872 KB Output is correct
17 Correct 66 ms 10724 KB Output is correct
18 Correct 111 ms 19552 KB Output is correct
19 Correct 110 ms 12384 KB Output is correct
20 Correct 49 ms 7272 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Correct 9 ms 1020 KB Output is correct
18 Correct 25 ms 1528 KB Output is correct
19 Correct 75 ms 2536 KB Output is correct
20 Correct 267 ms 4708 KB Output is correct
21 Correct 602 ms 4708 KB Output is correct
22 Correct 586 ms 8924 KB Output is correct
23 Correct 543 ms 2664 KB Output is correct
24 Correct 590 ms 4708 KB Output is correct
25 Correct 478 ms 33516 KB Output is correct
26 Correct 483 ms 17280 KB Output is correct
27 Correct 512 ms 17104 KB Output is correct
28 Correct 437 ms 33596 KB Output is correct
29 Correct 545 ms 33432 KB Output is correct
30 Correct 528 ms 17104 KB Output is correct
31 Correct 557 ms 2668 KB Output is correct
32 Correct 409 ms 1148 KB Output is correct
33 Correct 529 ms 17232 KB Output is correct
34 Correct 560 ms 33468 KB Output is correct
35 Correct 385 ms 33488 KB Output is correct
36 Correct 0 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 2 ms 512 KB Output is correct
40 Correct 12 ms 1528 KB Output is correct
41 Correct 5 ms 640 KB Output is correct
42 Correct 5 ms 1148 KB Output is correct
43 Correct 6 ms 1148 KB Output is correct
44 Correct 12 ms 1912 KB Output is correct
45 Correct 26 ms 1400 KB Output is correct
46 Correct 1633 ms 36464 KB Output is correct
47 Correct 52 ms 4072 KB Output is correct
48 Correct 388 ms 35256 KB Output is correct
49 Correct 768 ms 36164 KB Output is correct
50 Correct 705 ms 5480 KB Output is correct
51 Correct 111 ms 11872 KB Output is correct
52 Correct 66 ms 10724 KB Output is correct
53 Correct 111 ms 19552 KB Output is correct
54 Correct 110 ms 12384 KB Output is correct
55 Correct 49 ms 7272 KB Output is correct
56 Correct 2001 ms 4960 KB Output is correct
57 Execution timed out 4072 ms 33964 KB Time limit exceeded
58 Halted 0 ms 0 KB -