oj.uz

답안 #490068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490068 2021-11-25T11:48:43 Z keta_tsimakuridze 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 288 ms 33688 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 6 ms 972 KB Output is correct
6 Correct 7 ms 1320 KB Output is correct
7 Correct 9 ms 1484 KB Output is correct
8 Correct 11 ms 2148 KB Output is correct
9 Correct 26 ms 3820 KB Output is correct
10 Correct 51 ms 7472 KB Output is correct
11 Correct 63 ms 8556 KB Output is correct
12 Correct 132 ms 17216 KB Output is correct
13 Correct 167 ms 19908 KB Output is correct
14 Correct 220 ms 26196 KB Output is correct
15 Correct 230 ms 27924 KB Output is correct
16 Correct 247 ms 29072 KB Output is correct
17 Correct 283 ms 30416 KB Output is correct
18 Correct 258 ms 31428 KB Output is correct
19 Correct 266 ms 31408 KB Output is correct
20 Correct 288 ms 33688 KB Output is correct