Submission #31060

#	Time	Username	Problem	Language	Result	Execution time	Memory
31060		top34051	Jousting tournament (IOI12_tournament)	C++14	0 / 100	13 ms	2652 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
int n;
int sum[maxn], p[maxn], cnt[maxn];
int L[maxn], R[maxn];
int tree[maxn];
vector<int> temp;
set<int> act;

void update(int x,int val) {
    while(x<=n) {
        tree[x] += val;
        x += x&-x;
    }
}

int query(int x) {
    int res = 0;
    while(x>0) {
        res += tree[x];
        x -= x&-x;
    }
    return res;
}

int findpos(int x) {
    int l,r,mid,res=0;
    l = 1; r = n;
    while(l<=r) {
        mid = (l+r)/2;
        if(query(mid)<=x) res = mid, l = mid+1;
        else r = mid-1;
    }
    return res;
}

int GetBestPosition(int N, int C, int X, int *K, int *S, int *E) {
    int i,j,l,r,ans;
    set<int>::iterator it;
    n = N;
    for(i=1;i<=n;i++) sum[i] = sum[i-1] + (K[i-1]>X);
    for(i=0;i<C;i++) L[i] = S[i]+1, R[i] = E[i]+1;
    for(i=1;i<=n;i++) update(i,1), act.insert(i);
    for(i=0;i<C;i++) {
        l = findpos(L[i]-1)+1; r = findpos(R[i]);
//        printf("%d : [%d, %d]\n",i,l,r);
        temp.clear();
        for(it=act.lower_bound(l);it!=act.end() && *it<=r;++it) temp.push_back(*it);
        for(j=0;j<temp.size();j++) update(temp[j],-1), act.erase(temp[j]);
        update(l,1); act.insert(l);
        if(sum[r-1]-sum[l-1]==0) cnt[l]++; cnt[r+1]--;
    }
    ans = 0;
    for(i=1;i<=n;i++) {
        cnt[i] += cnt[i-1];
        ans = max(ans,cnt[i]);
    }
    return ans;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<temp.size();j++) update(temp[j],-1), act.erase(temp[j]);
                  ^

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