Submission #777227

#TimeUsernameProblemLanguageResultExecution timeMemory
777227OrazBExhibition (JOI19_ho_t2)C++17
100 / 100
60 ms4808 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <functional> using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; //Dijkstra->set //set.find_by_order(x) x-position value //set.order_of_key(x) number of strictly less elements don't need *set.?? #define N 100005 #define wr cout << "Continue debugging\n"; #define all(x) (x).begin(), (x).end() #define ll long long int #define pii pair <int, int> #define pb push_back #define ff first #define ss second int main () { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<pii> a(n+1); for (int i = 1; i <= n; i++) cin >> a[i].ss >> a[i].ff; vector<int> c(m+1); for (int i = 1; i <= m; i++) cin >> c[i]; sort(all(c)); sort(all(a)); vector<int> cur(n+1, -1); for (int i = 1; i <= n; i++){ if (c[m] < a[i].ss) continue; cur[i] = 1+m-(lower_bound(c.begin()+1, c.end(), a[i].ss)-c.begin()); } int l = 1, r = n, ans = 0; while(l <= r){ int md = (l+r)>>1; int x = 0, tr = 0; for (int i = 1; i <= n; i++){ if (cur[i] >= md-x) x++; if (x == md){tr=1;break;} } if (tr){ ans = md; l = md + 1; }else r = md - 1; } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...