Submission #400780

#	Time	Username	Problem	Language	Result	Execution time	Memory
400780		FlippenFaz	Jousting tournament (IOI12_tournament)	C++11	0 / 100	24 ms	3444 KiB

tournament

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

typedef long long ll;

#define SIZE 131072


int N;
int C;
int R;
int temp;

vector<int> corRange;
vector<int> knights;
vector<int> winPos;

int queryKnights(int l, int r) {
    l+=SIZE;
    r+=SIZE;
    int mx = -1;
    while (l <= r) {
        if (l%2 == 1) {
            mx = max(mx, knights[l++]);
        }
        if (r%2 == 0) {
            mx = max(mx, knights[r--]);
        }
        l/=2;
        r/=2;
    }
    return mx;
}

int queryRange(int l, int r) {
    l+=SIZE;
    r+=SIZE;
    int out = 0;
    while (l <= r) {

        //cout << "LEFT RIGHT" << l << " " << r << endl;
        if (l%2 == 1) {
            //cout << "ADDING LEFT" << endl;
            out += corRange[l++];
        }
        if (r%2 == 0) {
            //cout << "ADDING RIGHT" << endl;
            out += corRange[r--];
        }
        l/=2;
        r/=2;
    }
    return out;
}

void updateRange(int pos, int val) {
    pos += SIZE;
    corRange[pos] += val;
    while (pos > 0) {
        pos/=2;
        corRange[pos] = corRange[pos*2] + corRange[pos*2+1];
    }
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

    corRange.resize(SIZE+1);
    corRange.resize(SIZE*2, 1);

    //cout << "RANGE????" << endl;

    for (int i = SIZE-1; i > 0; i--) {
        corRange[i] = corRange[i*2] + corRange[i*2+1];
    }
    //cout << "SUM OF RANGE: " << corRange[1] << endl;
    //cout << "querey 0 1: " << queryRange(0,1) << endl;
    //cout << "STUFF:: " << corRange[SIZE] << " " << corRange[SIZE+1] << endl;

    //cout << "DOING KNIGHTS" << endl;

    knights.resize(SIZE);
    for (int i = 0; i < N-1; i++) {
        knights.push_back(K[i]);
    }
    knights.resize(SIZE*2);

    //cout << "KNIGHTS IN" << endl;

    for (int i = SIZE-1; i > 0; i--) {
        knights[i] = max(knights[i*2], knights[i*2+1]);
    }

    winPos.resize(N);

    //cout << "GOT INPS" << endl;

    for (int i = 0; i < C; i++) {
        //cout << "SI, EI: " << S[i] << " " << E[i] << endl;

        int left = queryRange(0, S[i]-1)+1;
        if (S[i] == 0) { left = 0; };

        //cout << "ADD THESE" << corRange[SIZE+0] << " " << corRange[SIZE+1] << endl;
        //cout << queryRange(0, 1) << endl;
        //cout << queryRange(0, E[i]) << endl;
        int right = queryRange(0, E[i]);
        if (queryKnights(left, right-1) < R) {
            winPos[left]++;
            winPos[right+1]--;
        }
        //cout << "LEFT RIGHT " << left << " " << right << " : " << right - left << endl;
        updateRange(S[i], E[i] - S[i]);

    }

    ll mx = -1;
    ll mxPos = -1;
    ll cur = 0;

    //cout << "got here" << endl;

    for (int i = 0; i < N; i++) {
        cur += winPos[i];
        //cout << winPos[i] << " ";
        if (cur > mx) {
            mx = cur;
            mxPos = i;
        }
    }
    //cout << "MAX: " << mx << " POS: " << mxPos << endl;
    //cout << endl;

    return mxPos;

};

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51