oj.uz

답안 #342066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342066 2021-01-01T09:36:08 Z 8e7 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 330 ms 25456 KB 
//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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 3 ms 2924 KB Output is correct
4 Correct 3 ms 2924 KB Output is correct
5 Correct 6 ms 3308 KB Output is correct
6 Correct 8 ms 3564 KB Output is correct
7 Correct 9 ms 3308 KB Output is correct
8 Correct 13 ms 3820 KB Output is correct
9 Correct 28 ms 5192 KB Output is correct
10 Correct 46 ms 5888 KB Output is correct
11 Correct 72 ms 8832 KB Output is correct
12 Correct 157 ms 15352 KB Output is correct
13 Correct 186 ms 16888 KB Output is correct
14 Correct 225 ms 20080 KB Output is correct
15 Correct 246 ms 18928 KB Output is correct
16 Correct 278 ms 19952 KB Output is correct
17 Correct 285 ms 23152 KB Output is correct
18 Correct 235 ms 16752 KB Output is correct
19 Correct 293 ms 24432 KB Output is correct
20 Correct 330 ms 25456 KB Output is correct