oj.uz

답안 #632996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632996 2022-08-21T11:33:58 Z gromperen 사다리꼴 (balkan11_trapezoid) C++14
60 / 100
 119 ms 27728 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
using pii = pair<int,long long>;

const int MOD = 30013;
const int INF = 1e9+7;
const int MAXN = 2e5+69;

pii fen[MAXN+5];

void upd(int i, pii v) {
	i++;
	for (; i < MAXN; i += (i & -i)) {
		if (fen[i].first < v.first) {
			fen[i].first = v.first;
			fen[i].second = v.second % MOD;
		} else if (fen[i].first == v.first) {
			fen[i].second += v.second;
			fen[i].second %= MOD;
		}

	}
}

pii query(int i) {
	i++;
	pii ans = {-1, 0};

	for (; i > 0; i -= (i & -i)) {
		if (fen[i].first > ans.first) {
			ans.first = fen[i].first;
			ans.second = fen[i].second;
		} else if (fen[i].first == ans.first) {
			ans.second += fen[i].second;
			ans.second %= MOD;
		}
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; cin >> n;
	vector<pair<pii, pii>> v(n+2);
	vector<int> a(n+2), b(n+2), c(n+2), d(n+2);
	vector<int> coords;
	for (int i = 0; i <n ; ++i) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		coords.push_back(a[i]);
		coords.push_back(b[i]);
		coords.push_back(c[i]);
		coords.push_back(d[i]);
	}
	// to avoid using neutral element
	coords.push_back(0);
	coords.push_back(INF);
	a[n] = b[n] = c[n] = d[n] = 0;
	a[n+1] = b[n+1] = c[n+1] = d[n+1] = INF;


	sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()));
	vector<int> id(coords.size()+5,-1);
	for (int i = 0; i <= n+1; ++i) {
		a[i] = lower_bound(coords.begin(), coords.end(), a[i]) - coords.begin();
		b[i] = lower_bound(coords.begin(), coords.end(), b[i]) - coords.begin();
		c[i] = lower_bound(coords.begin(), coords.end(), c[i]) - coords.begin();
		d[i] = lower_bound(coords.begin(), coords.end(), d[i]) - coords.begin();
		id[a[i]] = id[b[i]] = i;
	}

	upd(0, {1,1}); // add trap at 0 to avoid using neutral element
	vector<pii> dp(n+5);
	for (int i = 1; i < coords.size();++i) {
		if (id[i]==-1) continue;
		int cur = id[i];
		if (i == a[cur]) {
			dp[cur] = query(c[cur]);
			dp[cur].first++;
		}
		if (i == b[cur]) {
			upd(d[cur], dp[cur]);
		}
	}
	pii ans = query(MAXN-5);
	cout << ans.first - 2 << " " << ans.second % MOD << "\n";







	return 0;
}

Compilation message

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

Subtask #1
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 4 ms 988 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 10 ms 2008 KB Output is correct
10 Correct 19 ms 3436 KB Output is correct
11 Correct 27 ms 4636 KB Output is correct
12 Correct 54 ms 8660 KB Output is correct
13 Runtime error 71 ms 19972 KB Execution killed with signal 11
14 Runtime error 80 ms 21256 KB Execution killed with signal 11
15 Runtime error 96 ms 23368 KB Execution killed with signal 11
16 Runtime error 97 ms 24244 KB Execution killed with signal 11
17 Runtime error 100 ms 25148 KB Execution killed with signal 11
18 Runtime error 100 ms 25928 KB Execution killed with signal 11
19 Runtime error 100 ms 23844 KB Execution killed with signal 11
20 Runtime error 119 ms 27728 KB Execution killed with signal 11