Submission #92310

#	Time	Username	Problem	Language	Result	Execution time	Memory
92310		maruii	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	313 ms	17212 KiB

matryoshka

#include<bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define ff first
#define ss second
const int SIZE = 1<<18;
struct ST{
	int data[2*SIZE];
	void update(int x, int v){
		for(x+=SIZE; x; x/=2)
			data[x] = max(data[x], v);
	}
	int query(int s, int e){
		int ret = 0;
		for(s+=SIZE, e+=SIZE; s<=e; s/=2, e/=2){
			if(s&1) ret = max(ret, data[s++]);
			if(~e&1) ret = max(ret, data[e--]);
		}
		return ret;
	}
}seg;
ii p[200001];
pair<ii, int> qr[200001];
int ans[200001];
vector<int> xx,yy;
int main(){
	int N,Q; scanf("%d%d",&N,&Q);
	for(int i=0; i<N; ++i){
		int x, y; scanf("%d%d",&x, &y);
		p[i] = {-x, y};
		xx.push_back(-x);
		yy.push_back(y);
	}
	sort(xx.begin(), xx.end());
	sort(yy.begin(), yy.end());
	xx.erase(unique(xx.begin(), xx.end()), xx.end());
	yy.erase(unique(yy.begin(), yy.end()), yy.end());
	for(int i=0; i<N; ++i) p[i].ss = lower_bound(yy.begin(), yy.end(), p[i].ss) - yy.begin() + 1;
	sort(p, p+N);
	for(int i=0; i<Q; ++i){
		int x, y; scanf("%d%d",&x,&y);
		x = -x;
		y = upper_bound(yy.begin(), yy.end(), y) - yy.begin();
		qr[i] = {{x, y}, i};
	}
	sort(qr, qr+Q);
	for(int i=0, j=0; i<Q; ++i){
		while(j<N && p[j].ff<=qr[i].ff.ff){
			seg.update(p[j].ss, seg.query(0, p[j].ss)+1);
			++j;
		}
		ans[qr[i].ss] = seg.query(0, qr[i].ff.ss);
	}
	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:27:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N,Q; scanf("%d%d",&N,&Q);
           ~~~~~^~~~~~~~~~~~~~
matryoshka.cpp:29:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d",&x, &y);
             ~~~~~^~~~~~~~~~~~~~~
matryoshka.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d",&x,&y);
             ~~~~~^~~~~~~~~~~~~~

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