제출 #59477

#제출 시각아이디문제언어결과실행 시간메모리
59477ngkan146팀들 (IOI15_teams)C++11
34 / 100
4102 ms75116 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; #define l first #define r second int n; ii range[500000]; void init(int N, int A[], int B[]) { n = N; for(int i=0;i<n;i++) range[i] = {A[i], B[i]}; sort(range, range+n); } int can(int m, int lst[]) { set <int> s; int tmp = 0; for(int i=0;i<m && tmp <= n && s.size() <= 448;i++){ tmp = min(n+1, tmp + lst[i]); s.insert(lst[i]); } if (s.size() > 448 || tmp > n) return 0; int newM = 0; int ask[500] = {}, askTimes[500] = {}; for(set<int>::iterator it = s.begin(); it != s.end(); it++){ ask[newM++] = *it; } for(int i=0;i<m;i++){ askTimes[lower_bound(ask,ask+newM,lst[i]) - ask] ++; } multiset <int> current; int pivot = 0; for(int i=0;i<newM;i++){ while(pivot < n && range[pivot].l <= ask[i]){ current.insert(range[pivot++].r); } while(current.size() && *current.begin() < ask[i]) current.erase(current.begin()); if ((int)current.size() < ask[i] * askTimes[i]) return 0; for(int _=0;_<ask[i] * askTimes[i];_++) current.erase(current.begin()); } 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...