oj.uz

Submission #28152

# Submission time Handle Problem Language Result Execution time Memory
28152 2017-07-15T13:41:40 Z zoomswk Teams (IOI15_teams) C++14
13 / 100
 633 ms 149684 KB 
#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[]){

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

    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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 136796 KB Output is correct
2 Correct 3 ms 136796 KB Output is correct
3 Correct 0 ms 136796 KB Output is correct
4 Correct 6 ms 136796 KB Output is correct
5 Correct 0 ms 136796 KB Output is correct
6 Correct 3 ms 136796 KB Output is correct
7 Correct 3 ms 136796 KB Output is correct
8 Correct 6 ms 136796 KB Output is correct
9 Correct 3 ms 136796 KB Output is correct
10 Correct 3 ms 136796 KB Output is correct
11 Correct 6 ms 136796 KB Output is correct
12 Correct 0 ms 136796 KB Output is correct
13 Incorrect 0 ms 136796 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 139428 KB Output is correct
2 Correct 76 ms 139428 KB Output is correct
3 Correct 79 ms 139428 KB Output is correct
4 Correct 99 ms 139820 KB Output is correct
5 Correct 26 ms 138240 KB Output is correct
6 Correct 9 ms 138240 KB Output is correct
7 Correct 26 ms 138240 KB Output is correct
8 Correct 23 ms 138240 KB Output is correct
9 Correct 19 ms 138432 KB Output is correct
10 Correct 16 ms 138432 KB Output is correct
11 Correct 19 ms 138432 KB Output is correct
12 Correct 23 ms 138432 KB Output is correct
13 Correct 23 ms 138500 KB Output is correct
14 Correct 53 ms 139188 KB Output is correct
15 Correct 59 ms 139296 KB Output is correct
16 Correct 63 ms 139296 KB Output is correct
17 Correct 9 ms 138156 KB Output is correct
18 Correct 16 ms 138128 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 139824 KB Output is correct
2 Correct 89 ms 139820 KB Output is correct
3 Correct 179 ms 142504 KB Output is correct
4 Correct 69 ms 139820 KB Output is correct
5 Correct 73 ms 138636 KB Output is correct
6 Correct 59 ms 138636 KB Output is correct
7 Correct 39 ms 138636 KB Output is correct
8 Correct 53 ms 138636 KB Output is correct
9 Correct 29 ms 138432 KB Output is correct
10 Correct 19 ms 138460 KB Output is correct
11 Correct 16 ms 138440 KB Output is correct
12 Correct 53 ms 138568 KB Output is correct
13 Incorrect 93 ms 138768 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 633 ms 149684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -