Submission #1105405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105405		Amaarsaa	Poklon (COCI17_poklon)	C++14	0 / 140	274 ms	60488 KiB

poklon

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
using pll = pair < ll, ll >;
struct S {
	ll lo, hi, ind;
};
struct P {
	ll max_ind, max_val;
};
bool cmp(S A, S B ) {
	if (A.lo != B.lo) return A.lo < B.lo;
	return A.hi > B.hi;
}
const int N = 1e6 + 2;
ll A[N];
P T[8 * N];
void Build(ll p, ll lo, ll hi) {
	if ( lo == hi) {
		T[p].max_ind = lo;
		T[p].max_val = 0;
		return ;
	}
	ll mid = (lo +hi)/2;
	Build(2 * p, lo, mid);
	Build(2 * p + 1, mid + 1, hi);
	if ( T[2 * p].max_val >= T[2 * p + 1].max_val) {
		T[p].max_val = T[2 * p].max_val;
		T[p].max_ind = T[2 * p].max_ind;
	}
	else {
		T[p].max_val = T[2 * p + 1].max_val;
		T[p].max_ind = T[2 * p + 1].max_ind;
	}
}
void Update(ll p, ll lo, ll hi, ll x, ll y) {
	if ( lo == hi) {
		T[p].max_val = y;
		return;
	}
	ll mid = (lo + hi)/2;
	if ( x <= mid) Update(2 * p, lo,mid, x, y);
	else Update(2 * p + 1, mid + 1, hi, x, y);
	if ( T[2 * p].max_val >= T[2 * p + 1].max_val) {
		T[p].max_val = T[2 * p].max_val;
		T[p].max_ind = T[2 * p].max_ind;
	}
	else {
		T[p].max_val = T[2 * p + 1].max_val;
		T[p].max_ind = T[2 * p + 1].max_ind;
	}
	return ;
}
P Find(ll p, ll lo, ll hi, ll l, ll r) {
	if ( lo > r || l > hi) return {1, -1};
	if ( l <= lo && hi <= r) {
		return T[p];
	}
	P lef, rig;
	ll mid = (lo + hi)/2;
	lef = Find(2 * p, lo, mid, l, r);
	rig = Find(2 * p + 1, mid + 1, hi, l, r);
	if ( lef.max_val >= rig.max_val) return lef;
	return rig;
}
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll t, n, m, ans, s, sum, x, y, r, p, i, j;

	cin >> n;
	A[0] = 0;
	S P[n + 2];
	Build(1, 1, 1e6);	
	for (i =1; i <= n; i ++) {
		cin >> P[i].lo >> P[i].hi;
		P[i].ind = i;
	}
	sort (P + 1, P + n + 1, cmp);
	ll b[n + 2], c[n + 2];
	
	for (i =1; i <= n; i ++) b[i] = P[i].hi;
	reverse(b + 1, b + n + 1);
	ans = 0;
	for (i = 1; i <= n; i ++) {
		r = Find(1, 1, 1e6, 1, b[i]).max_val + 1;
		c[i] = r;
		Update(1, 1, 1e6, b[i], r);
		
		ans = max(ans, r);
	}
	r = 1e9;
	vector < pair < ll, ll > > Ans;
	for (i = n; i >= 1; i --) {
	//	cout << c[i] << " "<< ans << endl;
		if ( ans == c[i]  ) {
			r = P[n - i + 1].hi;
			Ans.push_back({P[n - i + 1].lo, P[n - i + 1].hi});			
			ans --;
		}
	}
	cout << Ans.size() << endl;
	//reverse(Ans.begin(), Ans.end());
	for (i = 0; i < Ans.size(); i ++){
		cout << Ans[i].first << " "<< Ans[i].second << endl;
	}
}

Compilation message (stderr)

poklon.cpp: In function 'int main()':
poklon.cpp:107:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (i = 0; i < Ans.size(); i ++){
      |              ~~^~~~~~~~~~~~
poklon.cpp:72:5: warning: unused variable 't' [-Wunused-variable]
   72 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |     ^
poklon.cpp:72:11: warning: unused variable 'm' [-Wunused-variable]
   72 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |           ^
poklon.cpp:72:19: warning: unused variable 's' [-Wunused-variable]
   72 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                   ^
poklon.cpp:72:22: warning: unused variable 'sum' [-Wunused-variable]
   72 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                      ^~~
poklon.cpp:72:27: warning: unused variable 'x' [-Wunused-variable]
   72 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                           ^
poklon.cpp:72:30: warning: unused variable 'y' [-Wunused-variable]
   72 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                              ^
poklon.cpp:72:36: warning: unused variable 'p' [-Wunused-variable]
   72 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                                    ^
poklon.cpp:72:42: warning: unused variable 'j' [-Wunused-variable]
   72 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                                          ^

• Subtask 1: 0 / 140