oj.uz

답안 #347973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347973 2021-01-14T00:43:29 Z shrek12357 사다리꼴 (balkan11_trapezoid) C++14
36 / 100
 500 ms 8016 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <iomanip>
#include <bitset>
//#include "molecules.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0);

struct s {
	int x, y, x1, y1;
};

bool comp(s a, s b) {
	return min(a.x, a.x1) < min(b.x, b.x1);
}

const int MAXN = 1e5 + 5;

int BIT[MAXN];

void update(int idx, int val) {
	for (; idx < MAXN; idx += idx & -idx) {
		BIT[idx] = max(BIT[idx], val);
	}
}

int query(int idx) {
	int ret = 0;
	for (; idx > 0; idx -= idx & -idx) {
		ret = max(ret, BIT[idx]);
	}
	return ret;
}

int dp[MAXN];
ll ways[MAXN];

const int MOD = 30013;

int main() {
	int n;
	cin >> n;
	vector<pair<pair<int, int>, pair<int, int>>> nums;
	map<int, int> cc;
	vector<int> p;
	for (int i = 0; i < n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		p.push_back(a);
		p.push_back(b);
		p.push_back(c);
		p.push_back(d);
		nums.push_back({ {a, b}, {c, d} });
	}
	sort(p.begin(), p.end());
	sort(nums.begin(), nums.end());
	int cnt = 1;
	for (int i = 0; i < nums.size(); i++) {
		if (cc.find(p[i]) != cc.end()) {
			continue;
		}
		cc[p[i]] = cnt;
		cnt++;
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ways[i] = 1;
		for (int j = 0; j < i; j++) {
			if (nums[j].first.second < nums[i].first.first && nums[j].second.second < nums[i].second.first) {
				if (dp[j] > dp[i]) {
					dp[i] = dp[j];
					ways[i] = ways[j];
				}
				else if (dp[i] == dp[j]) {
					ways[i] += ways[j];
				}
			}
		}
		dp[i]++;
		ans = max(ans, dp[i]);
		//dp[i] = max(dp[i], dp[i - 1]);
	}
	ll tot = 0;
	for (int i = 0; i < n; i++) {
		if (dp[i] == ans) {
			tot += ways[i];
		}
	}
	cout << ans << " " << tot % MOD << endl;
}

Compilation message

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

Subtask #1
36.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Partially correct 3 ms 364 KB Partially correct
5 Correct 9 ms 492 KB Output is correct
6 Partially correct 18 ms 620 KB Partially correct
7 Partially correct 27 ms 640 KB Partially correct
8 Correct 32 ms 748 KB Output is correct
9 Correct 151 ms 1256 KB Output is correct
10 Execution timed out 535 ms 1632 KB Time limit exceeded
11 Execution timed out 899 ms 2784 KB Time limit exceeded
12 Execution timed out 1095 ms 4400 KB Time limit exceeded
13 Execution timed out 1091 ms 5160 KB Time limit exceeded
14 Execution timed out 1089 ms 6096 KB Time limit exceeded
15 Execution timed out 1095 ms 6028 KB Time limit exceeded
16 Execution timed out 1099 ms 6352 KB Time limit exceeded
17 Execution timed out 1037 ms 7304 KB Time limit exceeded
18 Execution timed out 1087 ms 5652 KB Time limit exceeded
19 Execution timed out 1095 ms 7760 KB Time limit exceeded
20 Execution timed out 1095 ms 8016 KB Time limit exceeded