oj.uz

Submission #259595

# Submission time Handle Problem Language Result Execution time Memory
259595 2020-08-08T03:35:51 Z 송준혁(#5058) 역사적 조사 (JOI14_historical) C++17
0 / 100
 8 ms 768 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<int,int> pii;

int N, Q, B=400;
LL A[101010], C[101010], ans[101010];
map<LL,LL> M;
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]);
	for (int i=1; i<=Q; i++) scanf("%d %d", &P[i].s, &P[i].e), P[i].id=i;
	sort(P+1, P+Q+1, [&](query a, query b){
		if (a.s/B == b.s/B) return a.e < b.e;
		return a.s < b.s;
	});
	int l=1, r=1;
	M[A[1]] = A[1];
	S.push(pii(A[1], A[1]));
	for (int i=1; i<=Q; i++){
		for (int j=r+1; j<=P[i].e; j++){
			M[A[j]] += A[j];
			S.push(pii(M[A[j]], A[j]));
		}
		for (int j=P[i].s; j<l; j++) {
			M[A[j]] += A[j];
			S.push(pii(M[A[j]], A[j]));
		}
		for (int j=P[i].e+1; j<=r; j++) {
			M[A[j]] -= 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]] -= 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 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:25:32: 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("%lld", &A[i]);
                           ~~~~~^~~~~~~~~~~~~~~
historic.cpp:26: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Incorrect 8 ms 768 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -