Submission #1145362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145362		thangdz2k7	Teams (IOI15_teams)	C++20	0 / 100	41 ms	14796 KiB

teams

#ifdef EVAL

#include "teams.h"

#endif // EVAL

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 5e5 + 5;

int n, a[MaxN], b[MaxN];
int q, m, k[MaxN], fl[MaxN], fr[MaxN];

void init(int N, int A[], int B[]){
    n = N;
    for (int i = 0; i < n; ++ i)
        fl[B[i]] ++, fr[A[i]] ++;

    for (int i = 1; i <= n; ++ i)
        fl[i] += fl[i - 1];

    for (int i = n; i >= 1; -- i)
        fr[i] += fr[i + 1];
}

int p[MaxN], s[MaxN];

int can(int M, int K[]){

    for (int i = M; i >= 1; -- i)
        s[i] = K[i - 1];

    s[0] = 0, s[m + 1] = 0;
    sort(s + 1, s + m + 1);
    vector <int> diff;
    for (int i = 1; i <= M; ++ i){
        p[i] = p[i - 1] + s[i];
        if (p[i] > n) return 0;

        if (s[i] != s[i - 1] || s[i] != s[i + 1])
            diff.push_back(i);
    }

    int sz = diff.size();
    for (int u = 0; u < sz; ++ u){
        int l = s[diff[u]];
        for (int v = u; v < sz; ++ v){
            int r = s[diff[v]];
            if (n - fl[l - 1] - fr[r + 1] < p[diff[v]] - p[diff[u] - 1])
                return 0;
        }
    }

    return 1;
}

#ifndef EVAL

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++ i)
        cin >> a[i] >> b[i];

    init(n, a, b);

    cin >> q;
    for (int loops = 0; loops < q; ++ loops){
        cin >> m;
        for (int i = 0; i < m; ++ i)
            cin >> k[i];

        cout << can(m, k) << "\n";
    }
}

#endif // EVAL

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