Submission #144733

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
144733	2019-08-17T15:39:22 Z	Sorting	trapezoid (balkan11_trapezoid)	C++14	30 / 100	275 ms	23160 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.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 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	2040 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	2680 KB	Output is correct
8	Incorrect	12 ms	2936 KB	Output isn't correct
9	Incorrect	21 ms	3964 KB	Output isn't correct
10	Correct	45 ms	6264 KB	Output is correct
11	Incorrect	52 ms	7200 KB	Output isn't correct
12	Incorrect	131 ms	12592 KB	Output isn't correct
13	Incorrect	151 ms	14632 KB	Output isn't correct
14	Incorrect	169 ms	16736 KB	Output isn't correct
15	Incorrect	211 ms	17812 KB	Output isn't correct
16	Incorrect	244 ms	18840 KB	Output isn't correct
17	Incorrect	239 ms	20016 KB	Output isn't correct
18	Correct	235 ms	20984 KB	Output is correct
19	Incorrect	236 ms	22076 KB	Output isn't correct
20	Incorrect	275 ms	23160 KB	Output isn't correct