제출 #144775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144775		Sorting	사다리꼴 (balkan11_trapezoid)	C++14	5 / 100	546 ms	43948 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 7;
const int mod = 30013;
const int inf = 1e9;

struct trap{
	int a, b, c, d;

	trap(){}
	trap(int a, int b, int c, int d){
		this -> a = a;
		this -> b = b;
		this -> c = c;
		this -> d = d;
	}
};

bool cmp1(trap lvalue, trap rvalue){
	return lvalue.a < rvalue.a;
}
bool cmp2(trap lvalue, trap rvalue){
	return lvalue.b < rvalue.b;
}

struct fenwick_tree{
	pair<int, int> arr[MAXN];

	fenwick_tree(){
		for(int i = 0; i < MAXN; ++i){
			arr[i] = {0, 0};
		}
	}

	void update(int idx, pair<int, int> val){
		for(; idx < MAXN; idx += (idx & -idx)){
			if(val.first > arr[idx].first){
				arr[idx] = val;
			}
			else{
				if(val.first == arr[idx].first){
					arr[idx].second += val.second;
					arr[idx].second %= mod;
				}
			}
		}
	}

	pair<int, int> query(int idx){
		pair<int, int> ans = {1, 1};
		for(; idx >= 1; idx -= (idx & -idx)){
			if(arr[idx].first + 1 > ans.first){
				ans = {arr[idx].first + 1, max(arr[idx].second, 1)};
			}
			else{
				if(arr[idx].first + 1 == ans.first){
					ans.second += arr[idx].second;
					ans.second  %=  mod;
				}
			}
		}

		return ans;
	}
};

fenwick_tree f;

pair<int, int> dp[MAXN];
trap t1[MAXN], t2[MAXN];
set<int> st1, st2;
map<int, int> mp1, mp2;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;

	cin >> n;

	for(int i = 0; i < n; ++i){
		cin >> t1[i].a >> t1[i].b >> t1[i].c >> t1[i].d;
		st1.insert(t1[i].a);
		st1.insert(t1[i].b);
		st2.insert(t1[i].c);
		st2.insert(t1[i].d);
	}

	int cnt1 = 1;
	for(int x: st1){
		mp1[x] = cnt1++; 
	}

	int cnt2 = 1;
	for(int x: st2){
		mp2[x] = cnt2++;
	}

	t1[n] = {2 * n + 1, 2 * n + 2, 2 * n + 1, 2 * n + 2};
	t2[n] = t1[n];

	for(int i = 0; i < n; ++i){
		t1[i].a = mp1[t1[i].a];
		t1[i].b = mp1[t1[i].b];
		t1[i].c = mp2[t1[i].c];
		t1[i].d = mp2[t1[i].d];

		t2[i] = t1[i];
	}

	sort(t1, t1 + n + 1, cmp1);
	sort(t2, t2 + n + 1, cmp2);

	for(int i = 0; i <= n; ++i){
		dp[i] = f.query(t1[i].c);
		f.update(t2[i].d, dp[i]);		
	}

	cout << dp[n].first - 1 << " " << dp[n].second << "\n";

	return 0;
}

• Subtask 1: 5 / 100