Submission #342066

#	Time	Username	Problem	Language	Result	Execution time	Memory
342066		8e7	사다리꼴 (balkan11_trapezoid)	C++14	100 / 100	330 ms	25456 KiB

trapezoid

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <map>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define maxn 400005
#define mod 30013
using namespace std;

struct obj{
	pii a, b;
	int val = 0;
	obj(int x, int y, int z, int w) {
		a.ff = x, a.ss = y, b.ff = z, b.ss = w;
	}
};
vector<obj> v;
inline bool cmp(obj p, obj q) {
	return p.a.ff < q.a.ff;
}
inline bool cmp2(int i, int j) {
	return v[i].b.ff > v[j].b.ff;
}
priority_queue<int, vector<int>, bool(*) (int, int)> pq(cmp2);
int bit[maxn];
void modify(int ind, int val) {
	for (;ind < maxn;ind += ind & (-ind)) bit[ind] = max(bit[ind], val);
}
int query(int ind) {
	int ret = 0;
	for (;ind > 0;ind -= ind & (-ind)) ret = max(ret, bit[ind]);
	return ret;
}

int bit2[maxn];
void modify2(int ind, int val) {
	for (;ind < maxn;ind += ind & (-ind)) bit2[ind] = (bit2[ind] + val) % mod;
}
int query2(int ind) {
	int ret = 0;
	for (;ind > 0;ind -= ind & (-ind)) ret = (ret + bit2[ind]) % mod;
	return ret;
}
vector<int> lis[100005];
int val[100005];
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	vector<int> num;
	for (int i = 0;i < n;i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		v.push_back(obj(c, a, d, b));
		num.push_back(a);num.push_back(b);num.push_back(c);num.push_back(d);
	}
	sort(num.begin(), num.end());
	map<int, int> mp;
	int cnt = 1;
	mp[num[0]] = cnt;
	for (int i = 1;i < num.size();i++) {
		if (num[i] > num[i - 1]) cnt++;
		mp[num[i]] = cnt;
	}
	for (int i = 0;i < n;i++) {
		v[i].a.ss = mp[v[i].a.ss], v[i].b.ss = mp[v[i].b.ss];
		v[i].a.ff = mp[v[i].a.ff], v[i].b.ff = mp[v[i].b.ff];
	}

	sort(v.begin(), v.end(), cmp);

	int ans1 = 0, ans2 = 0;
	for (int i = 0;i < n;i++) {
		while (pq.size() && v[pq.top()].b.ff < v[i].a.ff) {
			modify(v[pq.top()].b.ss, v[pq.top()].val);
			pq.pop();
		}
		v[i].val = query(v[i].a.ss - 1) + 1;
		lis[v[i].val].push_back(i);
		ans1 = max(ans1, v[i].val);
		pq.push(i);
	}

	for (int i = 1;i <= ans1;i++) {
		int ind = 0;
		for (int j:lis[i]) {
			if (i == 1) {
				val[j] = 1;
			} else {
				while (ind < lis[i - 1].size() && v[lis[i - 1][ind]].b.ff < v[j].a.ff) {
					modify2(v[lis[i - 1][ind]].b.ss, val[lis[i - 1][ind]]);
					ind++;
				}
				val[j] = query2(v[j].a.ss - 1);
			}
		}
		for (int j = 0;j < ind;j++) modify2(v[lis[i - 1][j]].b.ss, -val[lis[i - 1][j]]);
		sort(lis[i].begin(), lis[i].end(), cmp2);
		reverse(lis[i].begin(), lis[i].end());
	}
	for (int j:lis[ans1]) ans2 = (ans2 + val[j]) % mod;
	cout << ans1 << " " << ans2 << endl;

}
/*
7
1 3 1 9
4 7 2 8
11 15 4 12
10 12 15 19
16 23 16 22
20 22 13 25
30 31 30 31
 */

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 1;i < num.size();i++) {
      |                 ~~^~~~~~~~~~~~
trapezoid.cpp:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     while (ind < lis[i - 1].size() && v[lis[i - 1][ind]].b.ff < v[j].a.ff) {
      |            ~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100