Submission #319745

#	Time	Username	Problem	Language	Result	Execution time	Memory
319745		parsabahrami	Pilot (NOI19_pilot)	C++17	100 / 100	982 ms	146800 KiB

pilot

//! The Leader Of Retards Bemola
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 1e6 + 10;
const ll INF  = 8e18;
const ll MOD  = 1e9 + 7;
ll ps[MAXN], L[MAXN], R[MAXN], A[MAXN], Q[MAXN], mark[MAXN], n, q;
map<pll, vector<ll>> mp; stack<ll> st;

ll C2(ll x) {
	if (x < 0) return 0;
	return x * (x - 1) / 2;
}

int main() {
	scanf("%lld%lld", &n, &q);
	for (ll i = 1; i <= n; i++) scanf("%lld", &A[i]);
	A[0] = A[n + 1] = MOD;
	st.push(0);
	for (ll i = 1; i <= n; i++) {
		while (A[st.top()] <= A[i]) st.pop();
		L[i] = st.top() + 1;
		st.push(i);
	}
	while (sz(st)) st.pop();
	st.push(n + 1);
	for (ll i = n; i; i--) {
		while (A[st.top()] <= A[i]) st.pop();
		R[i] = st.top() - 1;
		st.push(i);
		mp[{L[i], R[i]}].push_back(i);
	}
	for (auto &i : mp) {
		sort(all(i.S));
		ll res = C2(i.F.S - i.F.F + 2), prv = i.F.F, h = A[i.S[0]];
		//printf("%lld %lld %lld\n", i.F.F, i.F.S, res);
		i.S.push_back(i.F.S + 1);
		for (ll j = 0; j < sz(i.S); j++) {
			res -= C2((i.S)[j] - prv + 1);
			//if (i.F.F == 1 && i.F.S == 2) printf("test %lld %lld\n", prv, i.S[j]);
			prv = i.S[j] + 1;
		}
		//printf("%lld %lld %lld\n", i.F.F, i.F.S, res);
		ps[h] += res;
	}
	partial_sum(ps, ps + MAXN, ps);
	for (ll i = 1; i <= q; i++) {
		ll x; scanf("%lld", &x);
		printf("%lld\n", ps[x]);
	}
    return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  scanf("%lld%lld", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
pilot.cpp:33:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  for (ll i = 1; i <= n; i++) scanf("%lld", &A[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~
pilot.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   ll x; scanf("%lld", &x);
      |         ~~~~~^~~~~~~~~~~~

• 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