Submission #109557

#	Time	Username	Problem	Language	Result	Execution time	Memory
109557		nvmdava	Jousting tournament (IOI12_tournament)	C++17	0 / 100	202 ms	3368 KiB

tournament

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

int fen[BIG];
int in[BIG];
int p[BIG];
int last[BIG];
int ans[BIG];

int find(int v){
    return in[v] == 1 ? v : p[v] = find(p[v]);
}

void upd(int loc){
    while(loc < BIG){
        fen[loc]++;
        loc += loc & -loc;
    }
}

int sum(int loc){
    int res = 0;
    while(loc){
        res += fen[loc];
        loc -= loc & -loc;
    }
    return res;
}

void rangeupd(int l, int r){
    while((l = find(p[l])) <= r){
        in[l] = 0;
        upd(l);
    }
}

int finder(int val){
    int res = 0;
    int id = 0;
    for(int i = 16; i >= 0; i--){
        if(res + fen[id + (1 << i)] <= val){
            id += 1 << i;
            res += fen[id];
        }
    }
    return id;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    for(int i = 1; i <= N; i++){
        p[i] = i + 1;
        in[i] = 1;
    }
    for(int i = 1; i < BIG; i++){
        fen[i] = i & -i;
    }

    for(int i = 0; i < N - 1; i++){
        last[i + 1] = last[i];
        if(K[i] > R) last[i + 1] = i + 1;
    }
    last[N] = last[N - 1];
    for(int i = 0; i < C; i++){
        S[i] = finder(S[i] + 1);
        E[i] = find(p[finder(E[i] + 1)]) - 1;
        cerr<<S[i]<<' '<<E[i]<<'\n';
        rangeupd(S[i], E[i]);
        if(last[E[i] - 1] < S[i]){
            ans[S[i]]++;
            ans[E[i] + 1]--;
        }
    }
    int ret = 1;
    for(int i = 1; i <= BIG; i++){
        ans[i] += ans[i - 1];
        if(ans[i] > ans[ret]) ret = i;
    }
    return ret - 1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:76:16: warning: iteration 131071 invokes undefined behavior [-Waggressive-loop-optimizations]
         ans[i] += ans[i - 1];
         ~~~~~~~^~~~~~~~~~~~~
tournament.cpp:75:22: note: within this loop
     for(int i = 1; i <= BIG; i++){
                      ^

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