oj.uz

Submission #31067

# Submission time Handle Problem Language Result Execution time Memory
31067 2017-08-06T15:08:32 Z top34051 Jousting tournament (IOI12_tournament) C++14
0 / 100
 13 ms 2576 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
int n;
int sum[maxn], p[maxn], cnt[maxn];
int tree[maxn];
vector<int> temp;
set<int> act;
vector<pair<int,int> > a;

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

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

int findpos(int x) {
    int l,r,mid,res=-1;
    l = 0; r = n-1;
    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 *L, int *R) {
    int i,j,l,r,ans;
    set<int>::iterator it;
    n = N;
    for(i=0;i<n;i++) sum[i] = sum[i-1] + ((i<n-1 && K[i]>X) ? 1 : 0);
    for(i=0;i<n;i++) update(i,1), act.insert(i);
//    for(i=0;i<C;i++) {
//        l = findpos(L[i])+1; r = findpos(R[i]+1);
////        printf("%d : [%d, %d]\n",i,l,r);
//        temp.clear();
//        for(it=act.find(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]--;
//    }
    for(i=0;i<C;i++) {
        it = act.begin();
        for(j=0;j<L[i];j++) it++;
        if(it!=act.end()) l = *it;
        else l = n;
        it = act.begin();
        for(j=0;j<=R[i];j++) it++;
        if(it!=act.end()) r = *it;
        else r = n;
        r--;
//        printf("%d : %d %d\n",i,l,r);
        for(j=l+1;j<=r;j++) act.erase(j);
        if(sum[r-1]-sum[l-1]==0) a.push_back({l,r});
    }
    ans = 0;
    for(i=0;i<n;i++) {
        int ok = 0;
        for(int j=0;j<a.size();j++) if(a[j].first<=i && a[j].second>=i) ok++;
        ans = max(ans,ok);
    }
    return ans;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<a.size();j++) if(a[j].first<=i && a[j].second>=i) ok++;
                      ^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2180 KB Output is correct
2 Incorrect 0 ms 2180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 2576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -