oj.uz

Submission #31076

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

void update(int pos,int l,int r,int x,int val) {
    if(l>x || r<x) return ;
    if(l==r) {
        tree[pos] += val;
        return ;
    }
    int mid = (l+r)/2;
    update(pos<<1,l,mid,x,val); update(pos<<1|1,mid+1,r,x,val);
    tree[pos] = tree[pos<<1] + tree[pos<<1|1];
}

int findpos(int pos,int l,int r,int val) {
    if(l==r) return l;
    int mid = (l+r)/2;
    if(tree[pos<<1]>=val) return findpos(pos<<1,l,mid,val);
    return findpos(pos<<1|1,mid+1,r,val-tree[pos<<1]);
}

int GetBestPosition(int N, int C, int X, int *K, int *L, int *R) {
    int i,j,l,r;
    pair<int,int> 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(1,0,n,i,1), act.insert(i);
    for(i=0;i<C;i++) {
        l = findpos(1,0,n,L[i]+1); r = findpos(1,0,n,R[i]+2)-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(1,0,n,temp[j],-1), act.erase(temp[j]);
        update(1,0,n,l,1); act.insert(l);
        if(sum[r-1]-sum[l-1]==0) cnt[l]++, cnt[r+1]--;
    }
    ans = {0,0};
    for(i=0;i<n;i++) cnt[i] += cnt[i-1], ans = max(ans,{cnt[i],-i});
    return -ans.second;
}

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4756 KB Output is correct
2 Correct 0 ms 4756 KB Output is correct
3 Correct 0 ms 4756 KB Output is correct
4 Correct 0 ms 4756 KB Output is correct
5 Correct 0 ms 4756 KB Output is correct
6 Correct 0 ms 4756 KB Output is correct
7 Correct 0 ms 4756 KB Output is correct
8 Correct 0 ms 4756 KB Output is correct
9 Correct 0 ms 4756 KB Output is correct
10 Correct 0 ms 4756 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4888 KB Output is correct
2 Correct 6 ms 5020 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 6 ms 5020 KB Output is correct
5 Correct 6 ms 5020 KB Output is correct
6 Correct 6 ms 5020 KB Output is correct
7 Correct 6 ms 5020 KB Output is correct
8 Correct 9 ms 5020 KB Output is correct
9 Correct 3 ms 5152 KB Output is correct
10 Correct 6 ms 5024 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 7528 KB Output is correct
2 Correct 179 ms 10652 KB Output is correct
3 Correct 93 ms 10676 KB Output is correct
4 Correct 173 ms 10652 KB Output is correct
5 Correct 183 ms 10352 KB Output is correct
6 Correct 249 ms 10388 KB Output is correct
7 Correct 176 ms 10652 KB Output is correct
8 Correct 193 ms 10652 KB Output is correct
9 Correct 99 ms 10688 KB Output is correct
10 Correct 116 ms 9900 KB Output is correct