176432025-08-24 10:34:29tomi7Hadjáratcpp17Futási hiba 0/10014ms11812 KiB
#include <bits/stdc++.h>
using namespace std;

/*
int gcd(int a, int b){
	while(b){
		a %= b;
		swap(a, b);
	}
	return a;
}

struct antseg{
	int gcd = -1;
	int num = 1;

	antseg(){}
	antseg(int n){gcd = n;}
	antseg(int n, int k){gcd = n; num = k;}
};


antseg& operator+(const antseg& lhs, const antseg& rhs){
	if(lhs.gcd == -1) return rhs;
	if(rhs.gcd == -1) return lhs;

	antseg ANT(gcd(lhs.gcd, rhs.gcd), 0);
	if(ANT.gcd == lhs.gcd) ANT.num += lhs.num;
	if(ANT.gcd == rhs.gcd) ANT.num += rhs.num;

	return ANT;
}

antseg& operator=(antseg& lhs, const antseg& rhs){
	lhs.gcd = rhs.gcd;
	lhs.num = rhs.num;

	return rhs;
}
*/


















struct pos{
	int a = 0, b = 0;

	int i = -1;
};

istream& operator>>(istream& in, pos &p){
	in >> p.a >> p.b;
}

bool operator>(const pos& lhs, const pos& rhs){
	if(lhs.a != rhs.a) return lhs.a > rhs.a;
	if(lhs.b != rhs.b) return lhs.b > rhs.b;
	return false;
}

bool operator<(const pos& lhs, const pos& rhs){
	if(lhs.a != rhs.a) return lhs.a < rhs.a;
	if(lhs.b != rhs.b) return lhs.b < rhs.b;
	return false;
}

int main(){
	int n;
	cin >> n;

	vector<set<pos>> last(n+1);
	vector<int> prev(n);
	pos temp;
	last[0].insert(temp);

	temp.a = INT_MAX;
	temp.b = INT_MAX;
	temp.i = -2;

	for(auto &s : last) s.insert(temp);

	int Max = 0;
	int Maxi = -1;

	for(int i = 0; i != n; i++){
		pos curr;
		cin >> curr;
		curr.i = i;

		int a = 0;
		int b = n+1;

		while(a+1 != b){
			int c = (a+b)/2;

			auto iter = lower_bound(last[c].begin(), last[c].end(), curr); iter--;

			if(iter->b < curr.b) a = c;
			else b = c;
		}

		auto iter = lower_bound(last[a].begin(), last[a].end(), curr); iter--;


		prev[i] = iter->i;

		auto nextgr = lower_bound(last[a+1].begin(), last[a+1].end(), curr);

		while(nextgr->b >= curr.b) nextgr = last[a+1].erase(nextgr);

		last[a+1].insert(curr);

		if(a+1 > Max){Max = a+1; Maxi = i;}
	}

	vector<int> out;

	while(Maxi != -1){
		out.push_back(Maxi);
		Maxi = prev[Maxi];
	}

	reverse(out.begin(), out.end());

	printf("%d\n", out.size());
	for(int i : out) printf("%d ", i+1);


	return 0;
}




RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/100
1Futási hiba0/01ms508 KiB
2Futási hiba0/07ms5940 KiB
3Futási hiba0/41ms316 KiB
4Futási hiba0/41ms316 KiB
5Futási hiba0/41ms572 KiB
6Futási hiba0/41ms316 KiB
7Futási hiba0/41ms512 KiB
8Futási hiba0/41ms316 KiB
9Futási hiba0/41ms316 KiB
10Futási hiba0/41ms564 KiB
11Futási hiba0/42ms820 KiB
12Futási hiba0/42ms1588 KiB
13Futási hiba0/62ms1588 KiB
14Futási hiba0/64ms2612 KiB
15Futási hiba0/64ms3912 KiB
16Futási hiba0/68ms5940 KiB
17Futási hiba0/68ms7224 KiB
18Futási hiba0/610ms8244 KiB
19Futási hiba0/69ms9528 KiB
20Futási hiba0/614ms11572 KiB
21Futási hiba0/613ms11812 KiB
22Futási hiba0/614ms11572 KiB