Submission #583682

#	Time	Username	Problem	Language	Result	Execution time	Memory
583682		hibiki	Jousting tournament (IOI12_tournament)	C++11	0 / 100	66 ms	11716 KiB

tournament

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

#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n,c,r;
vector<int> as[100005],rs[100005];
int rmq[100005][20];

int get_max(int l, int r)
{
    int j = log2(r - l);
    return max(rmq[l][j], rmq[r - (1<<j)][j]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    n = N, c = C, r = R;
    indexed_set<int> os;
    for(int i = 0; i < n - 1; i++)
        rmq[i][0] = K[i];
    for(int j = 1; j < 20; j++)
        for(int i = 0; i + (1<<j) - 1 < n; i++)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j - 1))][j - 1]);
    for(int i = 0; i <= n; i++)
        os.insert(i);
    for(int i = 0; i < c; i++)
    {
        int st = *os.find_by_order(S[i]);
        int ed = *os.find_by_order(E[i] + 1) - 1;

        for(int j = S[i] + 1; j <= E[i]; j++)
            os.erase(os.find_by_order(S[i] + 1));

        S[i] = st, E[i] = ed;
    }
    for(int i = 0; i < c; i++)
    {
        as[S[i]].pb(i);
        rs[E[i] + 1].pb(i);
    }
    int cnt = 0, ans = 0;
    for(int i = 0; i < n; i++)
    {
        for(auto j: rs[i])
        {
            // printf("%d %d %d\n",S[j],E[j],get_max(S[j], E[j]));
            if(get_max(S[j], E[j]) < r)
                cnt--;
        }
        for(auto j: as[i])
        {
            // printf("%d %d %d\n",S[j],E[j],get_max(S[j], E[j]));
            if(get_max(S[j], E[j]) < r)
                cnt++;
        }

        ans = max(ans, cnt);
        // printf("%d\n",ans);
    }
    return ans;
}

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