oj.uz

Submission #237585

# Submission time Handle Problem Language Result Execution time Memory
237585 2020-06-07T14:36:43 Z nicolaalexandra Jousting tournament (IOI12_tournament) C++14
0 / 100
 562 ms 28280 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

int n,r,c,i,j;

int aib[DIM*2],v[DIM],stramos[DIM*2][22],aint[DIM*4];
set <pair<int,int> > s;
pair<int,int> intv[DIM*2];

void update_aib (int p, int val){
    for (;p<=n;p+=(p&-p))
        aib[p] += val;
}
int query (int p){
    if (p <= 0)
        return 0;
    int sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}

int find_kth (int k){

    int st = 1, dr = n, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (query(mid) >= k){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }
    return sol;
}

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = v[st];
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod] = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);
    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

int query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y)
        return aint[nod];
    int mid = (st+dr)>>1, sol_st = 0, sol_dr = 0;
    if (x <= mid)
        sol_st = query (nod<<1,st,mid,x,y);
    if (y > mid)
        sol_dr = query ((nod<<1)|1,mid+1,dr,x,y);
    return max (sol_st,sol_dr);
}

int GetBestPosition (int N, int C, int R, int *K, int *S, int *E) {
    n = N, r = R+1, c = C;

    for (i=1;i<=n;i++){
        update_aib (i,1);
        s.insert(make_pair(i,i));
        intv[i] = make_pair(i,i);
    }

    int idx = n;

    for (i=1;i<=c;i++){
        idx++;

        int x = S[i-1] + 1, y = E[i-1] + 1;
        int poz = find_kth(x);

        set <pair<int,int> > :: iterator it = s.lower_bound(make_pair(poz,0)), it2;
        it2 = it;

        int maxi = 0, mini = INF;
        /// sterg tot intervalul care incepe la poz
        for (int pas=1;pas<=y-x+1;pas++){
            mini = min (mini,intv[it2->second].first);
            maxi = max (maxi,intv[it2->second].second);

            stramos[it2->second][0] = idx;

            update_aib(it2->first,-1);
            it2++;
        }

        s.erase(it,it2);
        s.insert(make_pair(poz,idx));
        update_aib(poz,1);
        intv[idx] = make_pair(mini,maxi);
    }

    for (j=1;j<=20;j++)
        for (i=1;i<=n+c;i++)
            stramos[i][j] = stramos[stramos[i][j-1]][j-1];

    v[1] = 0;
    for (i=2;i<=n;i++){
        if (K[i-2]+1 < r)
            v[i] = 0;
        else v[i] = 1;
    }

    build (1,1,n);

    int sol = 0, best_poz;
    for (i=1;i<=n;i++){

        /// vreau sa vad cat de mult ma pot duc in sus a.i. sa am numai 0 in subarbore
        int nod = i, nr = 0;
        for (j=20;j>=0;j--){
            int nod_aux = stramos[nod][j];
            if (!nod_aux)
                continue;

            int st = intv[nod_aux].first , dr = intv[nod_aux].second;
            int maxi = query (1,1,n,st,dr);
            if (!maxi){ /// e subarbore ok, deci pot sa urc
                nod = nod_aux;
                nr += (1<<j);
            }
        }

        if (nr > sol){
            sol = nr;
            best_poz = i;
        }

        if (i == n)
            break;

        /// fac swap intre v[i] si v[i+1]
        int aux = v[i], aux2 = v[i+1];
        update (1,1,n,i,aux2);
        update (1,1,n,i+1,aux);
        swap (v[i],v[i+1]);
    }

    return best_poz-1;

}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:156:21: warning: 'best_poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return best_poz-1;
                     ^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Incorrect 5 ms 512 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 20 ms 1664 KB Output is correct
3 Correct 10 ms 1280 KB Output is correct
4 Correct 18 ms 1664 KB Output is correct
5 Correct 17 ms 1664 KB Output is correct
6 Correct 14 ms 1536 KB Output is correct
7 Correct 19 ms 1664 KB Output is correct
8 Correct 18 ms 1664 KB Output is correct
9 Incorrect 9 ms 1152 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 11640 KB Output is correct
2 Correct 562 ms 28188 KB Output is correct
3 Correct 185 ms 17912 KB Output is correct
4 Correct 503 ms 28124 KB Output is correct
5 Correct 520 ms 27196 KB Output is correct
6 Correct 259 ms 24184 KB Output is correct
7 Correct 514 ms 28152 KB Output is correct
8 Correct 513 ms 28280 KB Output is correct
9 Incorrect 167 ms 17280 KB Output isn't correct
10 Halted 0 ms 0 KB -