Submission #329704

#TimeUsernameProblemLanguageResultExecution timeMemory
329704egod1537조화행렬 (KOI18_matrix)C++14
29 / 100
86 ms17260 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pi; struct Tuple { int a, b, c; }; bool operator<(const Tuple& t1, const Tuple& t2) { if (t1.a != t2.a) return t1.a < t2.a; if (t1.b != t2.b) return t1.b < t2.b; return t1.c < t2.c; } vector<Tuple> arr; int maxlis = 0; int dp[200001]; //lis 그래프 struct Graph { set<pi> g[200001]; void insert(int k, pi p) { if (g[k].empty()) g[k].insert(p); else { auto pos = g[k].lower_bound(p); //prev가 없을 때 if (pos == g[k].begin()) pos = (g[k].insert(p)).first; else { auto back = prev(pos); if (back->second > p.second) { if (back->first == p.first) g[k].erase(pos); pos = (g[k].insert(p)).first; } } if (pos != g[k].end()) { while (next(pos) != g[k].end()) { auto nxt = next(pos); if (pos->second <= nxt->second) g[k].erase(nxt); else break; } } } } bool ok(int k, pi p) { if (g[k].empty()) return true; auto pos = prev(g[k].upper_bound(p)); if (pos == g[k].end()) return false; return pos->second <= p.second; } }g; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); //while (true) { // int t, a, b; cin >> t>> a >> b; // if (t == 0) { // g.insert(0, { a, b }); // for (pi p : g.g[0]) // cout << "graph : " << p.first << " " << p.second << "\n"; // } // else { // cout << "ok : " << g.ok(0, {a, b}) << "\n"; // } //} int n, m; cin >> n >> m; arr.resize(m); for (int i = 0; i < m; i++) cin >> arr[i].a; for (int i = 0; i < m; i++) cin >> arr[i].b; if (n == 3) for (int i = 0; i < m; i++) cin >> arr[i].c; sort(arr.begin(), arr.end()); if (n == 2) { vector<int> dp; for (int i = 0; i < m; i++) { int idx = lower_bound(dp.begin(), dp.end(), arr[i].b) - dp.begin(); if (idx == dp.size()) dp.push_back(arr[i].b); else dp[idx] = arr[i].b; } cout << dp.size(); } else { int ans = 0; for (int i = 0; i < m; i++) { pi now = { arr[i].b, arr[i].c }; //어떤 mid_lis가 가능하면 0 ~ mid lis가 가능하므로 int lo = 0, hi = maxlis; while (lo <= hi) { int mid = (lo + hi) / 2; if (g.ok(mid, now)) lo = mid + 1; else hi = mid - 1; } //cout << now.first << " " << now.second << " " << lo << "\n"; dp[i] = lo; g.insert(dp[i], now); ans = max(ans, dp[i]); maxlis = max(maxlis, dp[i]); } cout << ans; } return 0; }

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:85:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    if (idx == dp.size()) dp.push_back(arr[i].b);
      |        ~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...