Submission #1063008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063008		belgianbot	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	197 ms	25328 KiB

matryoshka

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>
#define fi first
#define se second
#define int long long

using namespace std;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, Q; cin >> N >> Q;
	vector<pair<int,int>> a(N);
	vector<pair<pair<int,int>,int>> q(Q);
	vector<int> res(Q);
	for (int i = 0; i < N; i++) cin >> a[i].fi >> a[i].se;
	for (int i = 0; i < Q; i++) {cin >> q[i].fi.fi >> q[i].fi.se; q[i].se = i;}
	
	sort(a.rbegin(), a.rend());
	sort(q.rbegin(), q.rend());
	
	int j = 0, cnt = 0;
	ordered_set lis;
	for (int i = 0; i < Q; i++) {
		int ans = lis.order_of_key({q[i].fi.se + 1,-1});
		while (j < N && a[j].fi >= q[i].fi.fi) {
			vector<int> curr;
			int actual = a[j].fi;
			for (; j < N && a[j].fi == actual; j++) curr.push_back(a[j].se);
		
			for (int k = 0; k < curr.size(); k++) {
				auto up = lis.upper_bound({curr[k] + 1,-1});
				if (up == lis.end()) {
					if (curr[k] <= q[i].fi.se) ans++;
				}
				else {
					lis.erase(up);
					if ((*up).fi > q[i].fi.se && curr[k] <= q[i].fi.se) ans++;
				}
			}
			for (int k = 0; k < curr.size(); k++) lis.insert({curr[k], cnt++});
		}
		res[q[i].se] = ans;
	}
	
	for (int i = 0; i < Q; i++) cout << res[i] << '\n';
	return 0;
}
	
	

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:34:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for (int k = 0; k < curr.size(); k++) {
      |                    ~~^~~~~~~~~~~~~
matryoshka.cpp:44:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for (int k = 0; k < curr.size(); k++) lis.insert({curr[k], cnt++});
      |                    ~~^~~~~~~~~~~~~

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