답안 #144775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144775	2019-08-17T16:57:23 Z	Sorting	사다리꼴 (balkan11_trapezoid)	C++14	5 / 100	500 ms	43948 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(t2[i].d, dp[i]);		
	}

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

	return 0;
}

Subtask #1

5.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1912 KB	Output is correct
2	Incorrect	4 ms	1912 KB	Output isn't correct
3	Incorrect	5 ms	2168 KB	Output isn't correct
4	Incorrect	6 ms	2420 KB	Output isn't correct
5	Incorrect	9 ms	2808 KB	Output isn't correct
6	Incorrect	11 ms	3192 KB	Output isn't correct
7	Incorrect	14 ms	3704 KB	Output isn't correct
8	Incorrect	20 ms	4088 KB	Output isn't correct
9	Incorrect	38 ms	6264 KB	Output isn't correct
10	Incorrect	85 ms	10744 KB	Output isn't correct
11	Incorrect	98 ms	12792 KB	Output isn't correct
12	Incorrect	244 ms	23260 KB	Output isn't correct
13	Incorrect	307 ms	27512 KB	Output isn't correct
14	Incorrect	354 ms	31456 KB	Output isn't correct
15	Incorrect	425 ms	33672 KB	Output isn't correct
16	Incorrect	472 ms	35576 KB	Output isn't correct
17	Incorrect	468 ms	37928 KB	Output isn't correct
18	Incorrect	446 ms	39824 KB	Output isn't correct
19	Incorrect	468 ms	41780 KB	Output isn't correct
20	Execution timed out	546 ms	43948 KB	Time limit exceeded