Submission #28166

#	Time	Username	Problem	Language	Result	Execution time	Memory
28166		zoomswk	Teams (IOI15_teams)	C++14	100 / 100	2423 ms	333616 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1000005;
int T[MAX_N*25], L[MAX_N*25], R[MAX_N*25];
int root[MAX_N];
int nodecnt=2;

int N;

void build(int node, int l, int r){
    if(l == r) return;
    L[node] = nodecnt++;
    R[node] = nodecnt++;
    int mid = (l+r)>>1;
    build(L[node], l, mid);
    build(R[node], mid+1, r);
    return;
}

void upd(int prev, int node, int l, int r, int pos){
    if(l == r){
        T[node] = T[prev]+1;
        return;
    }
    int mid = (l+r)>>1;
    L[node] = L[prev], R[node] = R[prev];
    if(pos <= mid){
        L[node] = nodecnt++;
        upd(L[prev], L[node], l, mid, pos);
    } else{
        R[node] = nodecnt++;
        upd(R[prev], R[node], mid+1, r, pos);
    }
    T[node] = T[L[node]] + T[R[node]];
    return;
}

int qr(int node, int node2, int until, int cur_l, int cur_r){
    if(cur_r <= until) return T[node]-T[node2];
    if(cur_l > until) return 0;
    int mid = (cur_l+cur_r)>>1;
    return qr(L[node], L[node2], until, cur_l, mid) + qr(R[node], R[node2], until, mid+1, cur_r);
}

vector<int> r[500005];
int st_cnt[500005], en_cnt[500005];

void init(int n, int A[], int B[]){
    N = n;
    for(int i=0; i<N; i++) r[B[i]].push_back(A[i]), st_cnt[A[i]]++, en_cnt[B[i]]++;
    for(int i=1; i<=N; i++) st_cnt[i] += st_cnt[i-1], en_cnt[i] += en_cnt[i-1];
    root[0] = 1;
    build(1, 1, N);
    for(int i=1; i<=N; i++){
        root[i] = root[i-1];
        if(r[i].size()){
            int prev = root[i-1];
            root[i] = nodecnt++;
            upd(prev, root[i], 1, N, r[i][0]);
            for(int j=1; j<r[i].size(); j++){
                int prev = root[i];
                root[i] = nodecnt++;
                upd(prev, root[i], 1, N, r[i][j]);
            }
        }
    }
    return;
}

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

    long long sum = 0;
    for(int i=0; i<M; i++) sum += K[i];
    if(sum > N) return 0;

    sort(K, K+M);

    int A[M], CNT[M];
    int ptr = 0;
    for(int i=0; i<M; i++) A[i] = 0, CNT[i] = 0;
    for(int i=0; i<M; i++){
        if(i == 0 || K[i] != K[i-1]){
            A[ptr] = K[i];
            CNT[ptr++] = K[i];
        } else{
            CNT[ptr-1] += K[i];
        }
    }

    int cnt = 0;
    for(int i=0; i<ptr; i++){

        int prev = 0;
        if(i) prev = A[i-1];

        // remove done students
        cnt -= en_cnt[A[i]-1] - (prev > 0 ? en_cnt[prev-1] : 0);
        int done = 0;
        for(int j=0; j<i; j++){
            if(!CNT[j]) continue;
            int ok = qr(root[A[i]-1], root[prev-1], A[j], 1, N);
            ok = min(ok-done, CNT[j]);
            CNT[j] -= ok;
            cnt += ok;
            done += ok;
        }

        // add new students
        cnt += st_cnt[A[i]] - st_cnt[prev];

        if(cnt < CNT[i]) return 0;
        cnt -= CNT[i];

    }

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=1; j<r[i].size(); j++){
                           ^
teams.cpp:63:21: warning: declaration of 'prev' shadows a previous local [-Wshadow]
                 int prev = root[i];
                     ^
teams.cpp:59:17: note: shadowed declaration is here
             int prev = root[i-1];
                 ^

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