Submission #490068

#	Time	Username	Problem	Language	Result	Execution time	Memory
490068		keta_tsimakuridze	trapezoid (balkan11_trapezoid)	C++14	100 / 100	288 ms	33688 KiB

trapezoid

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
#define int long long
using namespace std;
const int N = 2e5 + 5, mod = 30013  ; // !
int a[N][5], n;
map<int,int> id;
pii tree[4 * N], dp[N];
void compress(vector<int> x) {
	sort(x.begin() ,x.end());
	int idx = 0;
	for(int i = 0; i < x.size(); i++) {
		if(!i || x[i] != x[i - 1]) idx++;
		id[x[i]] = idx;
	}
}
pii merge(pii a, pii b) {
	if(a.f == b.f) return {a.f, (a.s + b.s ) % mod};
	return max(a, b);
}
void upd(int u,int ind,int l,int r, pii a) {
	if(l > ind || r < ind) return;
	if(l == r) {
		tree[u] = a;
		return;
	}
	int mid = (l + r)/2;
	upd(2 * u, ind, l, mid, a); upd(2 * u + 1, ind, mid + 1, r, a);
	tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
pii get(int u,int st,int en,int l,int r) {
	if(l > en || r < st) return {0, 0};
	if(st <= l && r <= en) return tree[u];
	int mid = (l + r)/2;
	return merge(get(2 * u, st, en, l, mid), get(2 * u + 1,st,en, mid + 1, r));
}
main() {
	cin >> n;
	vector<int> x;
	vector<pair<int,pii> > y;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 4; j++) cin >> a[i][j];
		x.push_back(a[i][2]);
		x.push_back(a[i][3]);
		y.push_back({a[i][0], {i, 0}});
		y.push_back({a[i][1], {i, 1}});
	}
	compress(x);
	sort(y.begin(), y.end());
	for(int i = 0; i < y.size(); i++) {
		int idx = y[i].s.f;
		if(y[i].s.s == 0) {
			dp[idx] = get(1, 1, id[a[idx][2]] - 1, 1, 2 * n);
			dp[idx].f++;
			if(dp[idx].f == 1) dp[idx].s = 1;
		}
		else upd(1, id[a[idx][3]],1, 2 * n, dp[idx]);
	}
	cout << tree[1].f <<" " << tree[1].s;
}

Compilation message (stderr)

trapezoid.cpp: In function 'void compress(std::vector<long long int>)':
trapezoid.cpp:14:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
trapezoid.cpp: At global scope:
trapezoid.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main() {
      | ^~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:52:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0; i < y.size(); i++) {
      |                 ~~^~~~~~~~~~

• Subtask 1: 100 / 100