Submission #28143

#	Time	Username	Problem	Language	Result	Execution time	Memory
28143		zoomswk	Teams (IOI15_teams)	C++14	13 / 100	633 ms	149684 KiB

teams

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

const int MAX_N = 500005;
int T[MAX_N*20], L[MAX_N*20], R[MAX_N*20];
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 until, int cur_l, int cur_r){
    if(cur_r <= until) return T[node];
    if(cur_l > until) return 0;
    int mid = (cur_l+cur_r)>>1;
    return qr(L[node], until, cur_l, mid) + qr(R[node], 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[]){
    sort(K, K+M);
    int cnt = 0;

    stack<pair<int, int>> st; // {position used, remaining cnt}
    for(int i=0; i<M; i++){

        if(i == 0 || K[i] != K[i-1]){

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

            // Remove ended students
            cnt -= en_cnt[K[i]-1] - (prev > 0 ? en_cnt[prev-1] : 0);
            while(!st.empty()){
                int pos = st.top().first, rem = st.top().second;
                st.pop();
                int ok = qr(root[K[i]-1], pos, 1, N);
                if(prev) ok -= qr(root[prev-1], pos, 1, N);
                ok = min(ok, rem);
                rem -= ok;
                cnt += ok;
                if(rem > 0){
                    st.push({pos, rem});
                    break;
                }
            }

            // Add new students
            cnt += st_cnt[K[i]]-st_cnt[prev];

        }

        // Finalize the business with this group
        if(cnt < K[i]) return 0;
        cnt -= K[i];
        int topush = K[i];
        while(!st.empty()){
            if(st.top().first != K[i]) break;
            topush += st.top().second;
            st.pop();
        }
        st.push({K[i], topush});
    }
	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: 0 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23