Submission #1010656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010656		pcc	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	1786 ms	22060 KiB

matryoshka

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

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 4e5+10;
int N,Q;
pii arr[mxn];
int ans[mxn];
pii req[mxn];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i].fs>>arr[i].sc;
	for(int i = 1;i<=Q;i++)cin>>req[i].fs>>req[i].sc,arr[i+N] = pii(-i,req[i].sc);
	sort(arr+1,arr+N+Q+1,[](pii a,pii b){return a.sc == b.sc?a.fs>b.fs:a.sc<b.sc;});
	vector<int> lis;
	for(int i = 1;i<=N+Q;i++){
		cerr<<arr[i].fs<<','<<arr[i].sc<<endl;
		if(arr[i].fs<0){
			int id = -arr[i].fs;
			int lim = -req[id].fs;
			auto p = upper_bound(lis.begin(),lis.end(),lim)-lis.begin();
			ans[id] = p;
		}
		else{
			int val = -arr[i].fs;
			auto p = upper_bound(lis.begin(),lis.end(),val)-lis.begin();
			if(p == lis.size())lis.push_back(val);
			else lis[p] = val;
		}
	}
	for(int i = 1;i<=Q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:32:9: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    if(p == lis.size())lis.push_back(val);
      |       ~~^~~~~~~~~~~~~

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