제출 #347973

#제출 시각아이디문제언어결과실행 시간메모리
347973shrek12357사다리꼴 (balkan11_trapezoid)C++14
36 / 100
1099 ms8016 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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++) {
      |                  ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...