Submission #144778

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
144778	2019-08-17T17:19:42 Z	Sorting	trapezoid (balkan11_trapezoid)	C++14	5 / 100	293 ms	23928 KB

trapezoid

#include <bits/stdc++.h>

using namespace std;

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

struct line{
	int first, second;
	bool type;

	line(){}
};

bool cmp(line lvalue, line rvalue){
	return lvalue.first < rvalue.first;
}

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];
line 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[2 * i].first >> t[2 * i + 1].first >> t[2 * i].second >> t[2 * i + 1].second;
		st.insert(t[2 * i].second);
		st.insert(t[2 * i + 1].second);
	}

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

	for(int i = 0; i < 2 * n; i++){
		t[i].second = mp[t[i].second];
	}

	t[2 * n].first = inf;
	t[2 * n + 1].first = inf + 1;
	t[2 * n].second = 2 * n + 1;
	t[2 * n + 1].second = 2 * n + 2;

	for(int i = 0; i < 2 * n + 2; ++i){
		if(i & 1){
			t[i].type = false;
		}
		else{
			t[i].type = true;
		}
	}

	sort(t, t + 2 * n + 2, cmp);
	int cnt1 = 0, cnt2 = 0;
	for(int i = 0; i < 2 * n + 2; ++i){
		if(t[i].type){
			dp[cnt1++] = f.query(t[i].second);
			//cout << i << " iiii " << dp[cnt1 - 1].first << " " << dp[cnt1 - 1].second << " - " << cnt1 - 1 << endl;
		}
		else{
			//cout << "update " << t[i].second << " " << dp[cnt2].first << "," << dp[cnt2].second << endl;
			f.update(t[i].second, dp[cnt2++]);
		}	
	}

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

	return 0;
}

Subtask #1

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1912 KB	Output is correct
2	Incorrect	4 ms	1912 KB	Output isn't correct
3	Incorrect	4 ms	2040 KB	Output isn't correct
4	Incorrect	5 ms	2168 KB	Output isn't correct
5	Incorrect	7 ms	2424 KB	Output isn't correct
6	Incorrect	8 ms	2552 KB	Output isn't correct
7	Incorrect	10 ms	2808 KB	Output isn't correct
8	Incorrect	13 ms	3064 KB	Output isn't correct
9	Incorrect	23 ms	4220 KB	Output isn't correct
10	Incorrect	47 ms	6268 KB	Output isn't correct
11	Incorrect	57 ms	7388 KB	Output isn't correct
12	Incorrect	142 ms	12916 KB	Output isn't correct
13	Incorrect	164 ms	15048 KB	Output isn't correct
14	Incorrect	182 ms	17272 KB	Output isn't correct
15	Incorrect	229 ms	18536 KB	Output isn't correct
16	Incorrect	254 ms	19532 KB	Output isn't correct
17	Incorrect	251 ms	20728 KB	Output isn't correct
18	Incorrect	248 ms	21596 KB	Output isn't correct
19	Incorrect	250 ms	22680 KB	Output isn't correct
20	Incorrect	293 ms	23928 KB	Output isn't correct