Submission #144716

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
144716	2019-08-17T14:49:27 Z	Sorting	trapezoid (balkan11_trapezoid)	C++14	0 / 100	500 ms	31456 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];

	void update(int idx, pair<int, int> val){
		for(; idx >= 1; 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 < MAXN; idx += (idx & -idx)){
			if(arr[idx].first + 1 > ans.first){
				ans = {arr[idx].first + 1, arr[idx].second};
			}
			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, n + 1, n + 2};

	for(int i = 1; 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].d);
		f.update(t[i].c, dp[i]);
	}

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

	return 0;
}

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1031 ms	376 KB	Time limit exceeded
2	Execution timed out	1061 ms	376 KB	Time limit exceeded
3	Incorrect	3 ms	504 KB	Output isn't correct
4	Incorrect	4 ms	632 KB	Output isn't correct
5	Execution timed out	1074 ms	892 KB	Time limit exceeded
6	Execution timed out	1059 ms	1144 KB	Time limit exceeded
7	Execution timed out	1081 ms	1400 KB	Time limit exceeded
8	Execution timed out	1069 ms	1528 KB	Time limit exceeded
9	Incorrect	21 ms	2808 KB	Output isn't correct
10	Execution timed out	1056 ms	5400 KB	Time limit exceeded
11	Execution timed out	1068 ms	6648 KB	Time limit exceeded
12	Execution timed out	1064 ms	13048 KB	Time limit exceeded
13	Execution timed out	1052 ms	15636 KB	Time limit exceeded
14	Runtime error	181 ms	31456 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Incorrect	225 ms	19448 KB	Output isn't correct
16	Execution timed out	1042 ms	20592 KB	Time limit exceeded
17	Incorrect	239 ms	21940 KB	Output isn't correct
18	Execution timed out	1081 ms	23112 KB	Time limit exceeded
19	Incorrect	241 ms	24408 KB	Output isn't correct
20	Incorrect	290 ms	25736 KB	Output isn't correct