Submission #53197

#	Time	Username	Problem	Language	Result	Execution time	Memory
53197		ainta	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	455 ms	91016 KiB

matryoshka

#include<cstdio>
#include<algorithm>
using namespace std;
#define SZ 262144
int n, QC, IT[SZ+SZ], Res[201000];
struct point {
	int x, y, num;
	bool operator<(const point &p)const {
		return x != p.x ? x > p.x:y < p.y;
	}
}w[201000], Q[201000];
int X[201000], Y[201000];
int Max(int b, int e) {
	b += SZ, e += SZ;
	int r = 0;
	while (b <= e) {
		r = max(r, max(IT[b], IT[e]));
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	return r;
}
void Ins(int a, int b) {
	a += SZ;
	while (a) {
		IT[a] = max(IT[a], b);
		a >>= 1;
	}
}
int main() {
	int i, x, y;
	scanf("%d%d", &n, &QC);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &X[i],&Y[i]);
		w[i] = { X[i],Y[i],i };
	}
	sort(X + 1, X + n + 1);
	sort(Y + 1, Y + n + 1);
	for (i = 1; i <= QC; i++) {
		scanf("%d%d", &x, &y);
		x = lower_bound(X + 1, X + n + 1, x) - X;
		y = lower_bound(Y + 1, Y + n + 1, y + 1) - Y - 1;
		Q[i] = { x,y,i };
	}
	for (i = 1; i <= n; i++) {
		w[i].x = lower_bound(X + 1, X + n + 1, w[i].x) - X;
		w[i].y = lower_bound(Y + 1, Y + n + 1, w[i].y) - Y;
	}
	sort(w + 1, w + n + 1);
	sort(Q + 1, Q + QC + 1);
	int pv = 1;
	for (i = 1; i <= QC; i++) {
		while (pv<=n && w[pv].x >= Q[i].x) {
			Ins(w[pv].y, Max(1, w[pv].y) + 1);
			pv++;
		}
		Res[Q[i].num] = Max(1, Q[i].y);
	}
	for (i = 1; i <= QC; i++)printf("%d\n", Res[i]);
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &QC);
  ~~~~~^~~~~~~~~~~~~~~~~
matryoshka.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &X[i],&Y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

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