Submission #391801

#	Time	Username	Problem	Language	Result	Execution time	Memory
391801		maomao90	Pilot (NOI19_pilot)	C++14	100 / 100	618 ms	28860 KiB

pilot

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

#define MP make_pair
#define FI first
#define SE second
typedef pair <int, int> ii;
typedef long long ll;
#define INF 1000000005

int n, q;
stack<ii> stk;

ll fw[1000005];
void update(int i, ll v) {
	for (; i < 1000005; i += (i & -i)) fw[i] += v;
}
void update(int s, int e, ll v) {
	if (e < s) return;
	update(s, v);
	update(e + 1, -v);
}
ll query(int i) {
	ll res = 0;
	for (; i > 0; i -= (i & -i)) res += fw[i];
	return res;
}

int main() {
	scanf("%d%d", &n, &q);
	stk.emplace(INF, -1);
	for (int i = 0; i <= n; i++) {
		int h; 
		if (i == n) h = INF - 1;
		else scanf("%d", &h);
		while (stk.size() > 1 && h > stk.top().FI) {
			int tp, tpi; tie(tp, tpi) = stk.top(); stk.pop();
			int prv, prvi; tie(prv, prvi) = stk.top();
			ll d = i - prvi - 1;
			update(tp, min(prv, h) - 1, d * (d + 1) / 2);
		}
		stk.emplace(h, i);
	}
	for (int i = 0; i < q; i++) {
		int y; scanf("%d", &y);
		printf("%lld\n", query(y));
	}
	return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
pilot.cpp:35:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   else scanf("%d", &h);
      |        ~~~~~^~~~~~~~~~
pilot.cpp:45:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   int y; scanf("%d", &y);
      |          ~~~~~^~~~~~~~~~

• 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