Submission #144776

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
144776	2019-08-17T17:03:40 Z	Sorting	trapezoid (balkan11_trapezoid)	C++14	30 / 100	500 ms	43648 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 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(t1[i].d, dp[i]);		
	}

	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	5 ms	2168 KB	Output isn't correct
4	Correct	6 ms	2424 KB	Output is correct
5	Incorrect	9 ms	2808 KB	Output isn't correct
6	Incorrect	11 ms	3192 KB	Output isn't correct
7	Correct	14 ms	3576 KB	Output is correct
8	Incorrect	19 ms	3960 KB	Output isn't correct
9	Incorrect	38 ms	6008 KB	Output isn't correct
10	Correct	85 ms	10232 KB	Output is correct
11	Incorrect	101 ms	12360 KB	Output isn't correct
12	Incorrect	243 ms	22648 KB	Output isn't correct
13	Incorrect	318 ms	27004 KB	Output isn't correct
14	Incorrect	354 ms	30968 KB	Output isn't correct
15	Incorrect	438 ms	33212 KB	Output isn't correct
16	Incorrect	473 ms	35064 KB	Output isn't correct
17	Incorrect	471 ms	37368 KB	Output isn't correct
18	Correct	450 ms	39288 KB	Output is correct
19	Incorrect	468 ms	41336 KB	Output isn't correct
20	Execution timed out	568 ms	43648 KB	Time limit exceeded