Submission #1221393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221393		sleepntsheep	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	208 ms	9216 KiB

matryoshka

#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;

#define N 200000
#define Q 200000
#define A ( N + Q )
int n, q, ans[N], cc[A], tp;
pair<int, int> mt[N];
pair<pair<int, int>, int> my[N];

int ft[A];

void add(int p, int k) {
	for (; p < A; p |= p + 1)
		ft[p] += k;
}
int sum(int p) {
	int z = 0;
	for (; p > 0; p &= p - 1)
		z += ft[p - 1];
	return z;
}
int search(int k) {
	int pos = 0;
	for (int j = 1 << 20; j >>= 1; )
		if (pos + j <= A && ft[pos + j - 1] < k)
			pos += j, k -= ft[pos - 1];
	return pos;
}



int main() {
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &mt[i].second, &mt[i].first);
		cc[tp++] = mt[i].second;
	}

	for (int i = 0; i < q; ++i) {
		my[i].second = i;
		scanf("%d%d", &my[i].first.second, &my[i].first.first);
		cc[tp++] = my[i].first.second;
	}
	sort(cc, cc + tp);
	tp = unique(cc, cc + tp) - cc;
	for (int i = 0; i < n; ++i)
		mt[i].second = lower_bound(cc, cc + tp, mt[i].second) - cc;
	for (int i = 0; i < q; ++i)
		my[i].first.second = lower_bound(cc, cc + tp, my[i].first.second) - cc;

	for (int i = 0; i < n; ++i)
		mt[i].second *= -1;


	sort(my, my + q);
	sort(mt, mt + n);

	for (int p = 0, i = 0, j; p < q; ++p) {
		for (; i < n && mt[i].first <= my[p].first.first; i = j) {
			j = i;
			for (; j < n && mt[j].first == mt[i].first; ) ++j;

			for (int xx, k = i; k < j; ++k) {
				if (! (xx = sum(-mt[k].second)))
					;
				else {
					add(search(xx), -1);
				}
				add(-mt[k].second, 1);
			}
		}

		ans[my[p].second] = sum(N + N) - sum(my[p].first.second);
	}

	for (int i = 0; i < q; ++i)
		printf("%d\n", ans[i]);

	return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d%d", &n, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~
matryoshka.cpp:38:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |                 scanf("%d%d", &mt[i].second, &mt[i].first);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |                 scanf("%d%d", &my[i].first.second, &my[i].first.first);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49