Submission #299399

#	Time	Username	Problem	Language	Result	Execution time	Memory
299399		FlashGamezzz	trapezoid (balkan11_trapezoid)	C++17	14 / 100	200 ms	43760 KiB

trapezoid

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

using namespace std;
long n, dp[100005], dp2[100005], maxa[300000] = {}, suma[300000] = {};

void updf(long i, long s, long e, long v, long dm, long ds) {
	if (s > v || e < v) {
		return;
	}	if (s == e && s == v) {
		maxa[i] = dm; suma[i] = ds;
		return;
	}
	updf(2*i+1, s, (s+e)/2, v, dm, ds);
	updf(2*i+2, (s+e)/2+1, e, v, dm, ds);
	if (maxa[2*i+1] > maxa[2*i+2]){
		maxa[i] = maxa[2*i+1], suma[i] = suma[2*i+1];
	} else if (maxa[2*i+1] == maxa[2*i+2]){
		maxa[i] = maxa[2*i+1], suma[i] = suma[2*i+1]+suma[2*i+2];
	} else {
		maxa[i] = maxa[2*i+2], suma[i] = suma[2*i+2];
	}
}
void updh(long ind, long dm, long ds) {
	long a = 0, b = 0;	updf(a, b, n-1, ind, dm, ds);
}
pair<long, long> qf(long i, long s, long e, long l, long u) {
	if (s > e || s > u || e < l) {
		return make_pair(-1000, 0);
	}
	if (s >= l && e <= u) {
		return make_pair(maxa[i], suma[i]);
	}
	pair<long, long> a = qf(2*i+1, s, (s+e)/2, l, u), b = qf(2*i+2, (s+e)/2+1, e, l, u);
	if (a.first > b.first){
		return a;
	} else if (a.first < b.first){
		return b;
	} else {
		return make_pair(a.first, a.second+b.second);
	}
}
pair<long, long> qh(long l, long u) {
	long a = 0, b = 0; return qf(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;
	}
};

vector<long> cc; unordered_map<long, long> ccm;
vector<trap> pqa;
priority_queue<trap, vector<trap>, comp2> pqb;

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;
		cc.push_back(i3); cc.push_back(i4);
		pqa.push_back(trap(i1, i2, i3, i4));
	}
	sort(cc.begin(), cc.end());
	for (int i = 0; i < 2*n; i++){
		ccm.insert(make_pair(cc[i], i));
	}
	sort(pqa.begin(), pqa.end(), comp1);
	for (long i = 0; i < n; i++){
		pqa[i].i = i; pqa[i].c = ccm[pqa[i].c]+1; pqa[i].d = ccm[pqa[i].d]+1;
	}
	n = 2*n+1; updh(0, 0, 1);
	for (long i = 0; i < pqa.size(); i++){
		while (pqb.size() > 0 && pqb.top().b < pqa[i].a){
			updh(pqb.top().d, dp[pqb.top().i], dp2[pqb.top().i]); pqb.pop();
		}
		pair<long, long> temp = qh(0, pqa[i].c);
		dp[i] = temp.first+1; dp2[i] = temp.second;
		pqb.push(pqa[i]);
	}
	while (pqb.size() > 0){
		updh(pqb.top().d, dp[pqb.top().i], dp2[pqb.top().i]); pqb.pop();
	}
	pair<long, long> ans = qh(0, n-1);
	cout << ans.first << " " << ans.second << endl;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:95:21: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<trap>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for (long i = 0; i < pqa.size(); i++){
      |                   ~~^~~~~~~~~~~~

• Subtask 1: 14 / 100