Submission #1272863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272863		goulthen	Pilot (NOI19_pilot)	C++20	100 / 100	399 ms	69812 KiB

pilot

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second

const int MAXN = 1e6+10;
const int INF = 1e18+10;
int a[MAXN], lf[MAXN], rg[MAXN], ans[MAXN];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
	int n,q;cin >> n >> q;
	vector<pii> vals;
	rep(i,1,n) {
		cin >> a[i];
		vals.pb({a[i],i});
	}

	stack<int> stk;
	a[0] = INF, a[n+1] = INF;
	stk.push(0);
	rep(i,1,n) {
		while (a[i] > a[stk.top()]) stk.pop();
		lf[i] = stk.top();
		stk.push(i);
	}
	while (!stk.empty())stk.pop();
	stk.push(n+1);
	per(i,n,1) {
		while (a[i] >= a[stk.top()]) stk.pop();
		rg[i] = stk.top();
		stk.push(i);
	}

	vector<pii> qr;
	rep(i,1,q) {
		int x;cin >> x;
		qr.push_back({x,i});
	}
	sort(qr.begin(), qr.end(), greater<pii>());
	sort(vals.begin(), vals.end(),greater<pii>());

	int id = 0, anss = 0;
	for (auto &[x,i] : qr) {
		while (id < n && vals[id].fi > x) {
			int j = vals[id].se;
			anss+= (rg[j]-j)*(j-lf[j]);
			id++;
		}

		ans[i] = n*(n+1)/2 - anss;
	}

	rep(i,1,q) cout << ans[i] << '\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: 11 / 11