제출 #1191301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191301		onbert	팀들 (IOI15_teams)	C++17	77 / 100	4097 ms	162384 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
    int val, lhs, rhs;
};
const int maxn = 500005, maxN = 3.8e7 + 5;
int n;
vector<int> rr[maxn];

int cnter = 1;
node seg[maxN];
int startnode = 1;
void build(int id, int l, int r) {
    seg[id] = {0, -1, -1};
    if (l == r) return;
    int mid = (l+r)/2;
    seg[id].lhs = ++cnter;
    build(cnter, l, mid);
    seg[id].rhs = ++cnter;
    build(cnter, mid+1, r);
}
int update(int id, int l, int r, int target) {
    if (r < target || target < l) return id;
    seg[++cnter] = seg[id];
    id = cnter;
    if (l == r) {
        seg[id].val++;
        return id;
    }
    int mid = (l+r)/2;
    seg[id].lhs = update(seg[id].lhs, l, mid, target);
    seg[id].rhs = update(seg[id].rhs, mid+1, r, target);
    seg[id].val = seg[seg[id].lhs].val + seg[seg[id].rhs].val;
    return id;
}
int sum(int id, int l, int r, int findl, int findr) {
    if (r < findl || findr < l) return 0;
    if (findl <= l && r <= findr) return seg[id].val;
    int mid = (l+r)/2;
    return sum(seg[id].lhs, l, mid, findl, findr) + sum(seg[id].rhs, mid+1, r, findl, findr);
}

int strt[maxn];
int qry(int t, int l, int r) {
    return sum(strt[t], 1, n, l, r);
}


void init(int N, int A[], int B[]) {
    n = N, cnter = 1;
    for (int i=1;i<=n;i++) rr[i].clear();
    for (int i=0;i<n;i++) rr[A[i]].push_back(B[i]);
    build(1, 1, n);
    for (int i=1;i<=n;i++) {
        for (int j:rr[i]) startnode = update(startnode, 1, n, j);
        strt[i] = startnode;
    }
}

int can(int m, int A[]) {
	sort(A, A+m);
    int S = 0;
    vector<pair<int,int>> vec;
    for (int i=0;i<m;i++) {
        if (i == 0 || A[i] != A[i-1]) vec.push_back({A[i], A[i]});
        else vec.back().second += A[i];
        S += A[i];
    }
    if (S > n) return 0;
    int sz = vec.size();
    vec.push_back({n+1, 0}); // not in sz

    int diff[sz];
    for (int i=0;i<sz;i++) diff[i] = 0;
    for (int i=0;i<sz;i++) {
        int taken = 0;
        for (int j=i;j<sz;j++) {
            int cur = qry(vec[i].first, vec[j].first, vec[j+1].first-1);
            cur += diff[j];
            cur = min(vec[i].second - taken, cur);
            diff[j] -= cur;
            taken += cur;
        }
        // cout << i << " " << vec[i].first << " " << vec[i].second << endl;
        // for (int j=0;j<sz;j++) cout << diff[j] << " "; cout << endl;
        if (taken < vec[i].second) return 0;
    }
    return 1;
}

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