Submission #66203

#TimeUsernameProblemLanguageResultExecution timeMemory
66203junodeveloper조화행렬 (KOI18_matrix)C++17
100 / 100
609 ms108692 KiB
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define all(x) (x).begin(), (x).end() using namespace std; typedef long long ll; typedef long double ld; const int INF = 1e9 + 10; int m, n, a[3][200010]; set<pair<int,int> > st[200010]; pair<int,int> p[200010]; bool Check(int k, pair<int,int>& v) { auto it = st[k].lower_bound({v.first, -INF}); if(it == st[k].begin()) return 0; --it; return it->second < v.second; } void Push(int k, pair<int,int>& v) { auto it = st[k].lower_bound({v.first, INF}); if(it != st[k].begin()) { --it; if(it->second <= v.second) return; if(it->first < v.first) ++it; } while(it != st[k].end() && it->second >= v.second) it = st[k].erase(it); st[k].insert(v); } int main() { scanf("%d%d", &m, &n); for(int i=0; i<m; i++) for(int j=1; j<=n; j++) scanf("%d", &a[i][j]); vector<pair<int,pair<int,int> > > Vq; for(int i=1; i<=n; i++) Vq.push_back({a[0][i], {a[1][i], a[m == 3 ? 2 : 0][i]}}); sort(all(Vq)); int res = 0; for(int i=0; i<sz(Vq); i++) { int lo = 0, hi = i; while(lo < hi) { int mid = (lo + hi + 1) / 2; if(Check(mid, Vq[i].second)) lo = mid; else hi = mid - 1; } Push(lo+1, Vq[i].second); res = max(res, lo+1); } printf("%d", res); return 0; }

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &m, &n);
  ~~~~~^~~~~~~~~~~~~~~~
matrix.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...