제출 #605958

#제출 시각아이디문제언어결과실행 시간메모리
605958cheissmart팀들 (IOI15_teams)C++14
34 / 100
4097 ms347864 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; struct node { node *l, *r; int cnt; node() { l = r = nullptr; cnt = 0; } node (node *_l, node *_r) { l = _l, r = _r; cnt = (l ? l -> cnt : 0) + (r ? r -> cnt : 0); } }; vi ev[N]; node* h[N]; node* lc(node* t) { return t ? t -> l : nullptr; } node* rc(node* t) { return t ? t -> r : nullptr; } int ct(node* t) { return t ? t -> cnt : 0; } node* upd(node* t, int pos, int tl = 0, int tr = n) { if(tr - tl == 1) { node* tt = new node(); tt -> cnt = 1; return tt; } int tm = (tl + tr) / 2; if(pos < tm) return new node(upd(lc(t), pos, tl, tm), rc(t)); else return new node(lc(t), upd(rc(t), pos, tm, tr)); } int qry(node* x, node* y, int lb, int rb, int tl = 0, int tr = n) { if(!x && !y) return 0; if(lb <= tl && tr <= rb) return ct(y) - ct(x); int tm = (tl + tr) / 2; int ans = 0; if(lb < tm) ans += qry(lc(x), lc(y), lb, rb, tl, tm); if(rb > tm) ans += qry(rc(x), rc(y), lb, rb, tm, tr); return ans; } int find_who(node* x, node* y, int cnt, int tl = 0, int tr = n) { assert(ct(y) - ct(x) > cnt); if(tr - tl == 1) return tl; int tm = (tl + tr) / 2; if(ct(lc(y)) - ct(lc(x)) > cnt) return find_who(lc(x), lc(y), cnt, tl, tm); else return find_who(rc(x), rc(y), cnt - (ct(lc(y)) - ct(lc(x))), tm, tr); } 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]; }); for(int i = 0; i < n; i++) ev[l[p[i]]].PB(i); for(int i = 1; i <= n; i++) { h[i] = h[i - 1]; for(int j:ev[i]) h[i] = upd(h[i], j); } } 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(h[lb], h[rb], 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 dead = qry(h[lb], h[rb], 0, at_least); int who = find_who(h[lb], h[rb], need + dead); 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...