Submission #605859

#TimeUsernameProblemLanguageResultExecution timeMemory
605859cheissmartTeams (IOI15_teams)C++14
21 / 100
4062 ms18272 KiB
#include "teams.h" #include <bits/stdc++.h> #define F first #define S second #define V vector #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(v) int((v).size()) #define ALL(v) (v).begin(), (v).end() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; const int INF = 1e9 + 7, N = 5e5 + 7; int n; int l[N], r[N]; vi p; void init(int _n, int _l[], int _r[]) { n = _n; for(int i = 0; i < n; i++) l[i] = _l[i], r[i] = _r[i]; p = vi(n); iota(ALL(p), 0); sort(ALL(p), [&] (int x, int y) { return r[x] < r[y]; }); } int qry(int x, int lb, int rb) { int ans = 0; for(int i = lb; i < rb; i++) { if(l[p[i]] <= x) ans++; } return ans; } int find_who(int lb, int rb, int at_least, int cnt) { for(int i = at_least; i < n; i++) { if(lb < l[p[i]] && l[p[i]] <= rb) { if(cnt == 0) return i; cnt--; } } throw; } struct seg { int r, hi; }; int can(int m, int a[]) { if(accumulate(a, a + m, 0LL) > n) return 0; sort(a, a + m); V<seg> stk; stk.PB({0, n}); for(int i = 0, j = 0; i < m; i++) { while(j < n && r[p[j]] < a[i]) j++; while(stk.back().hi < j) { assert(SZ(stk)); stk.pop_back(); } int need = a[i], at_least = j; while(need && SZ(stk)) { int lb = stk.back().r, rb = a[i]; // (lb, rb] int cnt = qry(rb, at_least, stk.back().hi) - qry(lb, at_least, stk.back().hi); if(cnt < need) { at_least = stk.back().hi; stk.pop_back(); need -= cnt; } else if(cnt == need) { at_least = stk.back().hi; stk.pop_back(); stk.PB({a[i], at_least}); need -= cnt; break; } else { int who = find_who(lb, rb, at_least, need); stk.PB({a[i], who}); break; } } if(stk.empty()) return 0; } return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...