Submission #1276333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276333		quanaskinger	Matryoshka (JOI16_matryoshka)	C++17	51 / 100	2094 ms	9836 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;
int n, q, x, y;
struct point {
	long long l, w, idx;
	bool operator< (const point &a) const {
		return (a.l < l || (a.l == l && a.w > w));
	}
};
vector<vector<int>> cartons;
int main()
{
    cin >> n >> q;
    point arr[n + 5], arr2[n + 5];
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i].l >> arr[i].w;
        arr[i].idx = i;
        arr2[i] = arr[i];
    }
    sort(arr+1, arr+n+1);
   	while (q--) {
   		vector <long long> cur;
   		cin >> x >> y;
   		cerr << x << " " << y << "\n";
   		for (long long i = 1; i <= n; i++) {
   			if (arr[i].l >= x && arr[i].w <= y) {
   				if (cur.empty() || arr[i].w >= cur.back()) cur.push_back(arr[i].w);
   				else {
   					long long t = upper_bound(cur.begin(), cur.end(), arr[i].w) - cur.begin();
   					cur[t] = arr[i].w;
   				}
   			}
   		}
   		cout << cur.size() << "\n";
   	}
}

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