oj.uz

Submission #28166

# Submission time Handle Problem Language Result Execution time Memory
28166 2017-07-15T13:59:48 Z zoomswk Teams (IOI15_teams) C++14
100 / 100
 2423 ms 333616 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 314524 KB Output is correct
2 Correct 6 ms 314524 KB Output is correct
3 Correct 0 ms 314524 KB Output is correct
4 Correct 3 ms 314524 KB Output is correct
5 Correct 0 ms 314524 KB Output is correct
6 Correct 0 ms 314524 KB Output is correct
7 Correct 3 ms 314524 KB Output is correct
8 Correct 0 ms 314524 KB Output is correct
9 Correct 3 ms 314524 KB Output is correct
10 Correct 3 ms 314524 KB Output is correct
11 Correct 3 ms 314524 KB Output is correct
12 Correct 3 ms 314524 KB Output is correct
13 Correct 6 ms 314524 KB Output is correct
14 Correct 6 ms 314524 KB Output is correct
15 Correct 0 ms 314524 KB Output is correct
16 Correct 0 ms 314524 KB Output is correct
17 Correct 0 ms 314524 KB Output is correct
18 Correct 3 ms 314524 KB Output is correct
19 Correct 3 ms 314524 KB Output is correct
20 Correct 0 ms 314524 KB Output is correct
21 Correct 3 ms 314524 KB Output is correct
22 Correct 0 ms 314524 KB Output is correct
23 Correct 0 ms 314524 KB Output is correct
24 Correct 0 ms 314524 KB Output is correct
25 Correct 0 ms 314524 KB Output is correct
26 Correct 0 ms 314524 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 317156 KB Output is correct
2 Correct 86 ms 317156 KB Output is correct
3 Correct 79 ms 317156 KB Output is correct
4 Correct 86 ms 318204 KB Output is correct
5 Correct 26 ms 315968 KB Output is correct
6 Correct 29 ms 315968 KB Output is correct
7 Correct 19 ms 315968 KB Output is correct
8 Correct 19 ms 315968 KB Output is correct
9 Correct 29 ms 316168 KB Output is correct
10 Correct 23 ms 316160 KB Output is correct
11 Correct 29 ms 316160 KB Output is correct
12 Correct 23 ms 316160 KB Output is correct
13 Correct 29 ms 316228 KB Output is correct
14 Correct 59 ms 316916 KB Output is correct
15 Correct 73 ms 317024 KB Output is correct
16 Correct 69 ms 317024 KB Output is correct
17 Correct 26 ms 315884 KB Output is correct
18 Correct 23 ms 315856 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 317552 KB Output is correct
2 Correct 96 ms 317552 KB Output is correct
3 Correct 109 ms 320192 KB Output is correct
4 Correct 79 ms 318200 KB Output is correct
5 Correct 69 ms 316364 KB Output is correct
6 Correct 56 ms 316364 KB Output is correct
7 Correct 23 ms 316364 KB Output is correct
8 Correct 39 ms 316364 KB Output is correct
9 Correct 26 ms 316168 KB Output is correct
10 Correct 23 ms 316204 KB Output is correct
11 Correct 43 ms 316168 KB Output is correct
12 Correct 773 ms 316296 KB Output is correct
13 Correct 189 ms 316496 KB Output is correct
14 Correct 139 ms 318748 KB Output is correct
15 Correct 83 ms 317420 KB Output is correct
16 Correct 69 ms 317420 KB Output is correct
17 Correct 46 ms 316304 KB Output is correct
18 Correct 43 ms 316292 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 328204 KB Output is correct
2 Correct 653 ms 328204 KB Output is correct
3 Correct 709 ms 333616 KB Output is correct
4 Correct 663 ms 329632 KB Output is correct
5 Correct 259 ms 322000 KB Output is correct
6 Correct 199 ms 322000 KB Output is correct
7 Correct 103 ms 322132 KB Output is correct
8 Correct 193 ms 322000 KB Output is correct
9 Correct 73 ms 322392 KB Output is correct
10 Correct 116 ms 321592 KB Output is correct
11 Correct 1686 ms 321592 KB Output is correct
12 Correct 2423 ms 321592 KB Output is correct
13 Correct 959 ms 322480 KB Output is correct
14 Correct 866 ms 329784 KB Output is correct
15 Correct 603 ms 326896 KB Output is correct
16 Correct 543 ms 326948 KB Output is correct
17 Correct 169 ms 322716 KB Output is correct
18 Correct 159 ms 322424 KB Output is correct