Submission #172756

#	Time	Username	Problem	Language	Result	Execution time	Memory
172756		songc	Matryoshka (JOI16_matryoshka)	C++14	100 / 100	321 ms	12268 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, Q;
int T[202020];
int ans[202020];
pii A[202020];
vector<int> comp, L;

struct query{
	int a, b, id;
	bool operator<(const query &r)const{
		return a > r.a;
	}
} qu[202020];

void update(int k, int v){
	while (k<=N){
		T[k] = max(T[k], v);
		k += k&-k;
	}
}

int read(int k){
	int ret=0;
	while (k>0){
		ret = max(ret, T[k]);
		k ^= k&-k;
	}
	return ret;
}

int com(int k){return lower_bound(comp.begin(), comp.end(), k)-comp.begin()+1;}

int main(){
	scanf("%d %d", &N, &Q);
	for (int i=1; i<=N; i++){
		scanf("%d %d", &A[i].first, &A[i].second);
		comp.push_back(A[i].second);
	}
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	sort(A+1, A+N+1, [&](pii a, pii b){
		if (a.first == b.first) return a.second < b.second;
		return a.first > b.first;
	});
	for (int i=1; i<=Q; i++){
		scanf("%d %d", &qu[i].a, &qu[i].b);
		qu[i].id = i;
	}
	sort(qu+1, qu+Q+1);

	int t=1;
	for (int i=1; i<=Q; i++){
		while (A[t].first >= qu[i].a){
			int lis = upper_bound(L.begin(), L.end(), A[t].second)-L.begin()+1;
			if (lis > L.size()) L.push_back(A[t].second);
			else L[lis-1] = A[t].second;
			update(com(A[t].second), lis);
			t++;
		}

		int k = com(qu[i].b+1)-1;
		ans[qu[i].id] = read(k);
	}
	for (int i=1; i<=Q; i++) printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:59:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (lis > L.size()) L.push_back(A[t].second);
        ~~~~^~~~~~~~~~
matryoshka.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
matryoshka.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &A[i].first, &A[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &qu[i].a, &qu[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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