oj.uz

답안 #632997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632997 2022-08-21T11:35:57 Z gromperen 사다리꼴 (balkan11_trapezoid) C++17
60 / 100
 86 ms 14972 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];
vector<int> id(MAXN,-1);

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:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 1; i < coords.size();++i) {
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 4 ms 1660 KB Output is correct
8 Correct 6 ms 1756 KB Output is correct
9 Correct 10 ms 2404 KB Output is correct
10 Correct 19 ms 3416 KB Output is correct
11 Correct 26 ms 4420 KB Output is correct
12 Correct 57 ms 7200 KB Output is correct
13 Runtime error 59 ms 9872 KB Execution killed with signal 11
14 Runtime error 58 ms 11152 KB Execution killed with signal 11
15 Runtime error 85 ms 11828 KB Execution killed with signal 11
16 Runtime error 72 ms 12480 KB Execution killed with signal 11
17 Runtime error 76 ms 13120 KB Execution killed with signal 11
18 Runtime error 86 ms 13728 KB Execution killed with signal 11
19 Runtime error 85 ms 14360 KB Execution killed with signal 11
20 Runtime error 77 ms 14972 KB Execution killed with signal 11