Submission #557084

#	Time	Username	Problem	Language	Result	Execution time	Memory
557084		lunchbox	역사적 조사 (JOI14_historical)	C++17	100 / 100	737 ms	8636 KiB

historic

/*
https://oj.uz/problem/view/JOI14_historical
역사적 조사 (Historical)
*/
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int N = 100000, B = 350, Q = 100000;

vector<array<int, 3>> qq[(N - 1) / B + 1];

int kk[N], aa_[N];
stack<pair<LL, int>> stk;

void add(int a) {
	kk[a]++;
	stk.push({max(stk.top().first, (LL) kk[a] * aa_[a]), a});
}
void pop() {
	kk[stk.top().second]--;
	stk.pop();
}
LL best() {
	return stk.top().first;
}

void run() {
	static LL ans[Q];
	static int aa[N];
	vector<int> vv;
	int n, q;

	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		vv.push_back(aa[i]);
	}
	sort(vv.begin(), vv.end());
	vv.erase(unique(vv.begin(), vv.end()), vv.end());
	for (int i = 0; i < n; i++) {
		int v = aa[i];

		aa[i] = lower_bound(vv.begin(), vv.end(), aa[i]) - vv.begin();
		aa_[aa[i]] = v;
	}
	for (int i = 0; i < q; i++) {
		int l, r;

		scanf("%d%d", &l, &r), l--, r--;
		qq[l / B].push_back({r, l, i});
	}
	stk.push({0, -1});
	for (int b = 0; b <= (n - 1) / B; b++) {
		int r_ = min(n, (b + 1) * B), p = r_ - 1;

		sort(qq[b].begin(), qq[b].end());
		for (auto [r, l, i] : qq[b]) {
			if (r < r_) {
				for (int j = l; j <= r; j++)
					add(aa[j]);
				ans[i] = best();
				for (int j = l; j <= r; j++)
					pop();
			} else {
				while (p < r)
					add(aa[++p]);
				for (int j = l; j < r_; j++)
					add(aa[j]);
				ans[i] = best();
				for (int j = l; j < r_; j++)
					pop();
			}
		}
		while (stk.size() > 1)
			pop();
	}
	for (int i = 0; i < q; i++)
		printf("%lld\n", ans[i]);
}

int main() {
	run();
	return 0;
}

Compilation message (stderr)

historic.cpp: In function 'void run()':
historic.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
historic.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   scanf("%d", &aa[i]);
      |   ~~~~~^~~~~~~~~~~~~~
historic.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d%d", &l, &r), l--, r--;
      |   ~~~~~^~~~~~~~~~~~~~~~

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