Submission #1011124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011124		xnqs	Pilot (NOI19_pilot)	C++17	100 / 100	339 ms	52748 KiB

pilot

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

struct Query {
	int cap, idx;
	Query():
		cap(0), idx(0) {}
	Query(int cap, int idx):
		cap(cap), idx(idx) {}
};

struct DSUBootleg {
	int64_t ans = 0;
	int left[1000005];
	int right[1000005];
	
	void Activate(int pos) {
		left[pos] = right[pos] = pos;

		if (left[pos-1]) {
			left[pos] = left[pos-1];
			int l = left[pos-1];
			int r = pos-1;
			ans -= 1LL*(r-l+1)*(r-l+2)/2;
		}
		if (right[pos+1]) {
			right[pos] = right[pos+1];
			int l = pos+1;
			int r = right[pos+1];
			ans -= 1LL*(r-l+1)*(r-l+2)/2;
		}

		left[right[pos]] = left[pos];
		right[left[pos]] = right[pos];
		ans += 1LL*(right[pos]-left[pos]+1)*(right[pos]-left[pos]+2)/2;
	}

	int64_t GetAns() {
		return ans;
	}
};

int x, q;
int arr[1000005];
int64_t ret[1000005];
DSUBootleg dsu;
std::vector<int> sorted_pos;
std::vector<Query> queries;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> q;
	for (int i = 1; i <= x; i++) {
		std::cin >> arr[i];
		sorted_pos.emplace_back(i);
	}

	std::sort(sorted_pos.begin(),sorted_pos.end(),[&](int a, int b) {
		return arr[a] < arr[b];
	});

	for (int i = 0, tmp; i < q; i++) {
		std::cin >> tmp;
		queries.emplace_back(tmp,i);
	}

	std::sort(queries.begin(),queries.end(),[](const Query& a, const Query& b) {
		return a.cap < b.cap;
	});

	int scanline = 0;
	for (const auto& [cap, idx] : queries) {
		while (scanline<x&&arr[sorted_pos[scanline]]<=cap) {
			dsu.Activate(sorted_pos[scanline]);
			++scanline;
		}

		/*for (int i = 1; i <= x; i++) {
			std::cout << dsu.left[i] << " " << dsu.right[i] << "\n";
		}
		std::cout << "\n";*/

		ret[idx] = dsu.GetAns();
	}

	for (int i = 0; i < q; i++) {
		std::cout << ret[i] << "\n";
	}
}

• 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: 11 / 11