Submission #144729

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
144729	2019-08-17T15:21:08 Z	Sorting	trapezoid (balkan11_trapezoid)	C++14	30 / 100	277 ms	23032 KB

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 cmp(trap lvalue, trap rvalue){
	return lvalue.a < rvalue.a;
}

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 t[MAXN];
set<int> st;
map<int, int> mp;

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

	int n;

	cin >> n;

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

	int cnt = 1;
	for(int x: st){
		mp[x] = cnt++; 
	}

	t[n] = {inf - 1, inf, 2 * n + 1, 2 * n + 2};

	for(int i = 0; i < n; ++i){
		t[i].c = mp[t[i].c];
		t[i].d = mp[t[i].d];
	}

	sort(t, t + n + 1, cmp);

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

		//cout << dp[i].first << " " << dp[i].second << "\n";
	}

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

	return 0;
}

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1912 KB	Output is correct
2	Correct	4 ms	1912 KB	Output is correct
3	Incorrect	4 ms	2040 KB	Output isn't correct
4	Correct	5 ms	2044 KB	Output is correct
5	Incorrect	7 ms	2296 KB	Output isn't correct
6	Incorrect	8 ms	2552 KB	Output isn't correct
7	Correct	10 ms	2808 KB	Output is correct
8	Incorrect	13 ms	3024 KB	Output isn't correct
9	Incorrect	22 ms	4088 KB	Output isn't correct
10	Correct	45 ms	6136 KB	Output is correct
11	Incorrect	53 ms	7208 KB	Output isn't correct
12	Incorrect	133 ms	12516 KB	Output isn't correct
13	Incorrect	155 ms	14584 KB	Output isn't correct
14	Incorrect	177 ms	16760 KB	Output isn't correct
15	Incorrect	215 ms	17764 KB	Output isn't correct
16	Incorrect	236 ms	18880 KB	Output isn't correct
17	Incorrect	239 ms	19940 KB	Output isn't correct
18	Correct	231 ms	20984 KB	Output is correct
19	Incorrect	236 ms	22104 KB	Output isn't correct
20	Incorrect	277 ms	23032 KB	Output isn't correct