제출 #294484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294484		FlashGamezzz	사다리꼴 (balkan11_trapezoid)	C++17	15 / 100	148 ms	11612 KiB

trapezoid

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

struct trap {
	long a, b, c, d, i;
	trap(long i1, long i2, long i3, long i4){
		a = i1; b = i2; c = i3; d = i4; i = 0;
	}
};
struct comp1 {
	bool operator()(trap t1, trap t2){
		return t1.a > t2.a;
	}
};
struct comp2 {
	bool operator()(trap t1, trap t2){
		return t1.b > t2.b;
	}
};

long n, dp[100000], dp2[100001] = {};
priority_queue<trap, vector<trap>, comp1> pqa;
priority_queue<trap, vector<trap>, comp2> pqb;
map<long, long> mp;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (long i = 0; i < n; i++){
		long i1, i2, i3, i4;
		cin >> i1 >> i2 >> i3 >> i4;
		pqa.push(trap(i1, i2, i3, i4));
	}
	mp.insert(make_pair(-1, 0));
	for (int i = 0; i < n; i++){
		trap curr = pqa.top(); pqa.pop();
		map<long, long>::iterator temp;
		while (pqb.size() > 0 && pqb.top().b < curr.a){
			temp =mp.lower_bound(pqb.top().d); temp--;
			mp.insert(make_pair(pqb.top().d, max(dp[pqb.top().i], temp->second)));
			pqb.pop();
		}
		curr.i = i;
		temp = mp.lower_bound(curr.c); temp--;
		dp[i] = temp->second + 1;
		pqb.push(curr);
	}
	long a1 = 0;
	dp2[0] = 1;
	for (int i = 0; i < n; i++){
		dp2[dp[i]] += dp2[dp[i]-1];
		dp2[dp[i]] %= 30013;
		a1 = max(a1, dp[i]);
	}
	cout << a1 << " " << dp2[a1] << endl;
}

• Subtask 1: 15 / 100