Submission #364947

#	Time	Username	Problem	Language	Result	Execution time	Memory
364947		GioChkhaidze	trapezoid (balkan11_trapezoid)	C++14	100 / 100	398 ms	46912 KiB

trapezoid

#include <bits/stdc++.h>

#define lf (h << 1)
#define rf ((h << 1) | 1)
#define Tree int h, int l, int r
#define Left lf, l, (l + r) >> 1
#define Right rf, ((l + r) >> 1) + 1, r
#define pb push_back

using namespace std;

const int N = 1e5 + 5;

int n, T, mod = 30013;
int a[N], b[N], c[N], d[N];
vector < int > U[4 * N], G[4 * N]; 

struct node{
	int x;
	int c;
};

node v[16 * N], dp[N], bs;

void compress() {
	vector < int > s;
	map < int , int > f;
	for (int i = 1; i <= n; ++i) {
		s.pb(a[i]), s.pb(b[i]);
		s.pb(c[i]), s.pb(d[i]);
	}	
	
	sort(s.begin(), s.end());
	s.erase(unique(s.begin(), s.end()), s.end());
	T = s.size(); 
	
	for (int i = 0; i < s.size(); ++i) {
		f[s[i]] = i + 1;
	}
	
	for (int i = 1; i <= n; ++i) {
		a[i] = f[a[i]];
		b[i] = f[b[i]];
		c[i] = f[c[i]];
		d[i] = f[d[i]];
	}
}

node comb(node a, node b) {
	node d;
	d.x = max(a.x, b.x), d.c = 0;
	if (d.x == a.x) d.c = (d.c + a.c) % mod;
	if (d.x == b.x) d.c = (d.c + b.c) % mod;
	return d;
}

void upd(Tree, int id, node vl) {
	if (id < l || r < id) return ;
	if (id == l && id == r) {
		if (v[h].x == vl.x) 
			v[h].c = (v[h].c + vl.c) % mod; 
				else 
			v[h] = vl;		
		return ;
	}
	
	upd(Left, id, vl);
	upd(Right, id, vl);
	v[h] = comb(v[lf], v[rf]);
}

node get(Tree, int L, int R) {
	if (r < L || R < l) return bs;
	if (L <= l && r <= R) return v[h];
	return comb(get(Left, L, R), get(Right, L, R));
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	bs.c = bs.x = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}	
	
	compress();
	for (int i = 1; i <= n; ++i) {
		U[b[i]].pb(i);
		G[a[i]].pb(i);
	}
	
	for (int i = 1; i <= T; ++i) {
		for (int j = 0; j < G[i].size(); ++j) {
			int id = G[i][j];
			node res = get(1, 1, T, 1, c[id] - 1);
			if (!res.c) res.c = 1;
			++res.x;
			dp[id] = res;
		}
		
		for (int j = 0; j < U[i].size(); ++j) {
			int id = U[i][j];
			upd(1, 1, T, d[id], dp[id]);
		}		
	}
	
	cout << v[1].x << " " << v[1].c << "\n";
}

Compilation message (stderr)

trapezoid.cpp: In function 'void compress()':
trapezoid.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~
trapezoid.cpp: At global scope:
trapezoid.cpp:78:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main () {
      |       ^
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int j = 0; j < G[i].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~
trapezoid.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int j = 0; j < U[i].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100