oj.uz

Submission #364947

# Submission time Handle Problem Language Result Execution time Memory
364947 2021-02-10T14:20:47 Z GioChkhaidze trapezoid (balkan11_trapezoid) C++14
100 / 100
 398 ms 46912 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19180 KB Output is correct
2 Correct 13 ms 19180 KB Output is correct
3 Correct 14 ms 19308 KB Output is correct
4 Correct 15 ms 19436 KB Output is correct
5 Correct 18 ms 19820 KB Output is correct
6 Correct 21 ms 20224 KB Output is correct
7 Correct 21 ms 19948 KB Output is correct
8 Correct 26 ms 20332 KB Output is correct
9 Correct 43 ms 22116 KB Output is correct
10 Correct 63 ms 23216 KB Output is correct
11 Correct 93 ms 26596 KB Output is correct
12 Correct 191 ms 33748 KB Output is correct
13 Correct 241 ms 36280 KB Output is correct
14 Correct 292 ms 42516 KB Output is correct
15 Correct 313 ms 37448 KB Output is correct
16 Correct 345 ms 38904 KB Output is correct
17 Correct 374 ms 45864 KB Output is correct
18 Correct 264 ms 36316 KB Output is correct
19 Correct 350 ms 45580 KB Output is correct
20 Correct 398 ms 46912 KB Output is correct