Submission #295797

#	Time	Username	Problem	Language	Result	Execution time	Memory
295797		FlashGamezzz	trapezoid (balkan11_trapezoid)	C++14	40 / 100	191 ms	17060 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;
 
long n, dp[100005], inds[100005], inds2[100005], maxa[300000] = {};
void updf(long i, long s, long e, long v, long d) {
	if (s > v || e < v) {
		return;
	}
	if (s == e && s == v) {
		maxa[i] = d;
		return;
	}
	updf(i * 2 + 1, s, (s + e)/2, v, d);
	updf(i * 2 + 2, (s + e)/2 + 1, e, v, d);
	maxa[i] = max(maxa[i * 2 + 1], maxa[i * 2 + 2]);
}
void updh(long v, long d) {
	long a = 0, b = 0;
	updf(a, b, n-1, v, d);
}
long maxf(long i, long s, long e, long l, long u) {
	if (s > e || s > u || e < l) {
		return -1000;
	}
	if (s >= l && e <= u) {
		return maxa[i];
	}
	return max(maxf(2*i+1, s, (s+e)/2, l, u), maxf(2*i+2, (s+e)/2+1, e, l, u));
}
long maxh(long l, long u) {
	if (u < l){
		return 0;
	}
	long a = 0, b = 0;
	return maxf(a, b, n-1, l, u);
}
 
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;
	}
};
bool comp1 (trap t1, trap t2){
	return t1.a < t2.a;
}
struct comp2 {
	bool operator()(trap t1, trap t2){
		return t1.b > t2.b;
	}
};
struct comp3 {
	bool operator()(trap t1, trap t2){
		return t1.c > t2.c;
	}
};
struct comp4 {
	bool operator()(trap t1, trap t2){
		return t1.d > t2.d;
	}
};
 
vector<trap> pqa;
priority_queue<trap, vector<trap>, comp2> pqb;
priority_queue<trap, vector<trap>, comp3> pqc;
priority_queue<trap, vector<trap>, comp4> pqd;
 
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_back(trap(i1, i2, i3, i4));
	}
	sort(pqa.begin(), pqa.end(), comp1);
	for (long i = 0; i < n; i++){
		pqa[i].i = i; pqd.push(pqa[i]); pqc.push(pqa[i]);
	}
	for (long i = 0; i < n; i++){
		inds[pqd.top().i] = i;
		while (pqc.size() > 0 && pqc.top().c < pqd.top().d){
			inds2[pqc.top().i] = i-1; pqc.pop();
		}
		pqd.pop();
	}
	long a1 = 0;
	for (long i = 0; i < n; i++){
		trap curr = pqa[i];
		while (pqb.size() > 0 && pqb.top().b < curr.a){
			updh(inds[pqb.top().i], dp[pqb.top().i]); pqb.pop();
		}
		pqb.push(curr);
		dp[i] = maxh(0, inds2[curr.i])+1;
		a1 = max(a1, dp[i]);
	}
	cout << a1 % 30013 << " " << 0 << endl;
}

• Subtask 1: 40 / 100