Submission #650402

#	Time	Username	Problem	Language	Result	Execution time	Memory
650402		depro	Pilot (NOI19_pilot)	C++17	89 / 100	1065 ms	69772 KiB

pilot

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...);}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, q; cin >> n >> q;

	vector<pair<int, int>>a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a.begin(), a.end());

	vector<pair<int, int>>queries(q);
	for (int i = 0; i < q; i++) {
		cin >> queries[i].first;
		queries[i].second = i;
	}

	set<int> s({-1, n});
	sort(queries.rbegin(), queries.rend());

	auto cal = [&](int l, int r) {
		return 1LL * (r - l + 1) * (r - l + 2) / 2;
	};

	vector<long long>ans(q);
	int cur = n - 1;
	long long cnt = 1LL * n * (n + 1) / 2;

	for (auto [val, id] : queries) {
		while(cur >= 0 && a[cur].first > val) {
			auto it = s.lower_bound(a[cur].second);
			int r = *it; r--;
			int l = *(--it); l++;
			cnt -= cal(l, r);
			cnt += cal(l, a[cur].second - 1);
			cnt += cal(a[cur].second + 1, r);

			s.insert(a[cur].second);
			cur--;
		}

		ans[id] = cnt;
	}

	for (long long x : ans) cout << x << '\n';
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11