제출 #1139597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139597		anmattroi	Teams (IOI15_teams)	C++17	34 / 100	4090 ms	10820 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n, a[maxn], b[maxn], m, k[maxn];

struct event {
    int type, x, cnt = 0;
    event() {}
    event(int _type, int _x, int _cnt) : type(_type), x(_x), cnt(_cnt) {}

    bool operator < (const event &other) const {
        if (x != other.x) return x < other.x;
        return type < other.type;
    }
} e[3*maxn];

int cl[maxn];

int solve() {
    int id = 0;
    for (int i = 1; i <= n; i++) cl[i] = 0;
    for (int i = 1; i <= n; i++) e[++id] = event(1, a[i], i);
    for (int i = 1; i <= n; i++) e[++id] = event(3, b[i], i);
    for (int i = 1; i <= m; i++) e[++id] = event(2, k[i], k[i]);

    sort(e + 1, e + id + 1);
    set<ii> s;
    for (int o = 1; o <= id; o++) {
        auto [type, x, cnt] = e[o];
        if (type == 1) {
            s.insert(ii{b[cnt], cnt});
            continue;
        }
        if (type == 3) {
            s.erase(ii{b[cnt], cnt});
            continue;
        }
        if (s.size() < cnt) return 0;
        while (cnt--) s.erase(s.begin());
    }
    return 1;
}

void init(int N, int A[], int B[]) {
    n = 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];
}

int can(int M, int K[]) {
    m = M;
    for (int i = 1; i <= m; i++) k[i] = K[i-1];
	return solve();
}

/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1

1
0
*/

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