Submission #260942

#	Time	Username	Problem	Language	Result	Execution time	Memory
260942		onjo0127	역사적 조사 (JOI14_historical)	C++11	40 / 100	4053 ms	11240 KiB

historic

#include <bits/stdc++.h>
using namespace std;
const int bck = 320;

struct query {
	int s, e, id;
};

int X[100009], I[100009];
long long ans[100009], sum[100009];
multiset<long long> st;

void add(int x) {
	st.erase(st.find(sum[I[x]]));
	sum[I[x]] += X[x];
	st.insert(sum[I[x]]);
}

void del(int x) {
	st.erase(st.find(sum[I[x]]));
	sum[I[x]] -= X[x];
	st.insert(sum[I[x]]);
}

int main() {
	vector<query> S; vector<int> P;
	int N, Q; scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++) {
		scanf("%d", &X[i]);
		P.push_back(X[i]);
	}
	sort(P.begin(), P.end());
	P.resize(unique(P.begin(), P.end()) - P.begin());
	for(int i=1; i<=N; i++) I[i] = lower_bound(P.begin(), P.end(), X[i]) - P.begin() + 1;
	for(int i=1; i<=Q; i++) {
		int s, e; scanf("%d%d", &s, &e);
		S.push_back({s, e, i});
	}
	sort(S.begin(), S.end(), [&](query PP, query QQ) {
		int pb = PP.s / bck, qb = QQ.s / bck;
		if(pb == qb) return PP.e < QQ.e;
		return pb < qb;
	});

	for(int i=1; i<=P.size(); i++) st.insert(0);
	int s = 1, e = 0;
	for(auto& it: S) {
		int ns = it.s, ne = it.e;
		while(e < ne) add(++e);
		while(e > ne) del(e--);
		while(s > ns) add(--s);
		while(s < ns) del(s++);
		ans[it.id] = *st.rbegin();
	}
	for(int i=1; i<=Q; i++) printf("%lld\n", ans[i]);
	return 0;
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<=P.size(); i++) st.insert(0);
               ~^~~~~~~~~~
historic.cpp:27:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, Q; scanf("%d%d", &N, &Q);
            ~~~~~^~~~~~~~~~~~~~~~
historic.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &X[i]);
   ~~~~~^~~~~~~~~~~~~
historic.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d%d", &s, &e);
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60