| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 831657 | qin | 팀들 (IOI15_teams) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
struct st{
int a, b;
st(){}
st(int A, int B) : a(A), b(B) {}
bool operator <(const st &x) const{return b == x.b ? a < x.a : b < x.b;}
};
int base = 1;
int it = 0;
struct seg{
vector<int> t;
void init(int n){
while(base < n) base <<= 1;
t.resize(base<<1);
} void update(int i, int w){
i += base-1; t[i] = w;
for(i>>=1; i; i>>=1) t[i] = t[i<<1] + t[i<<1|1];
} int Find(int i, int pocz, int kon){
if(pocz == kon) return pocz;
int ret = 0;
if(t[i<<1]) ret = Find(i<<1, pocz, (pocz+kon)>>1);
else ret = Find(i<<1|1, ((pocz+kon)>>1)+1, kon);
return ret;
} int findsmallest(){
if(!t[1]) return 0;
else return Find(1, 1, base);
}
};
vector<vector<st>> v;
bool can(int n, int m, int T[]){
vector<int> t(m);
for(int i = 0; i < m; ++i) t[i] = T[i];
int suma = 0;
for(int i = 0; i < m; ++i) suma += t[i];
if(suma > n) return 0;
seg seg;
seg.init(n);
int it = 0, tmp;
sort(t.begin(), t.end());
bool b = 1;
for(int i = 1; i <= n; ++i){
for(st u : v[i]) seg.update(u.a, u.b);
while(it != m && t[it] == i){
for(int j = 1; j <= i; ++j){
if(!seg.t[1]) { b = 0; break; }
tmp = seg.findsmallest();
seg.update(tmp, 0);
} ++it;
}
} return b;
}
void init(int n, int A[], int B[]){
vector<int> a(n+1), b(n+1);
vector<st> t(n);
for(int i = 1; i <= n; ++i) a[i] = A[i-1];
for(int i = 1; i <= n; ++i) b[i] = B[i-1], t[i-1] = st(a[i], b[i]);
sort(t.begin(), t.end());
v.resize(n+2);
for(int i = 0; i < n; ++i) v[t[i].a].emplace_back(i+1, 1), v[t[i].b+1].emplace_back(i+1, 0);
}