Submission #200180

#	Time	Username	Problem	Language	Result	Execution time	Memory
200180		Mercenary	Teams (IOI15_teams)	C++14	34 / 100	4032 ms	38420 KiB

teams

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> ii;

#ifndef LOCAL
#include "teams.h"
#endif // LOCAL
const int maxn = 5e5 + 5;
ii a[maxn];
int n;

void init(int N, int A[], int B[]) {
    n = N;
    for(int i = 0 ; i < n ; ++i){
        a[i] = mp(A[i],B[i]);
    }
    sort(a,a+n);
}
#define Brute

int can(int M, int K[]) {
    #ifdef Brute
    sort(K,K+M);
    int it = 0;
    multiset<int> s;
    for(int i = 0 ; i < M ; ++i){
        int tmp = K[i];
        while(it < n && a[it].first <= tmp)s.insert(a[it++].second);
        while(K[i] > 0){
            if(s.size()){
                auto t = s.lower_bound(tmp);
                if(t != s.end()){
                    s.erase(s.find(*t));
                    --K[i];
                }else break;
            }else break;
        }
        if(K[i] > 0)return 0;
    }
    return 1;
    #else

    #endif
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("a.inp", "r")) {
        freopen("a.inp", "r", stdin);
        freopen("a.out", "w", stdout);
    }
    int N;
    cin >> N;
    int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
    int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
    for (int i = 0; i < N; ++i) {
    	cin >> A[i] >> B[i];
    }
    init(N, A, B);
    int Q;cin >> Q;
    for (int i = 0; i < Q; ++i) {
    	int M;cin >> M;
	int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
    	for (int j = 0; j < M; ++j) {
            cin >> K[j];
    	}
        cout << can(M,K) << '\n';
    }
    return 0;

}
#endif // LOCAL

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23