oj.uz

답안 #242368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242368 2020-06-27T11:51:55 Z dantoh000 마상시합 토너먼트 (IOI12_tournament) C++14
100 / 100
 198 ms 17528 KB 
#include <bits/stdc++.h>
using namespace std;
const int SZ = 100005;
typedef pair<int,int> ii;
int l[SZ], r[SZ], RR[SZ];
int fw[SZ];
int a[SZ];
void up(int x, int nv){
    x++;
    while (x < SZ){
        fw[x]+=nv;
        x += x&-x;
    }
}
int sum(int x){
    x++;
    int ret = 0;
    while (x){
        ret += fw[x];
        x -=x&-x;
    }
    return ret;
}
set<ii> pos;
struct node{
    int s,e,m,v;
    node *l, *r;
    node (int _s ,int _e): s(_s), e(_e){
        m = (s+e)/2;
        v = 0;
        if (s != e){
            l = new node(s,m);
            r= new node(m+1,e);
        }
    }
    void up(int x){
        if (s == e){
            v = 1; return;
        }
        if (x > m) r->up(x);
        else if (x <= m) l->up(x);
        v = l->v|r->v;
    }
    int query(int qs, int qe){
        if (qs == s && qe == e){ return v; }
        else{
            if (qs > m) return r->query(qs,qe);
            else if (qe <= m) return l->query(qs,qe);
            else return l->query(qs,m) | r->query(m+1,qe);
        }
    }

}*root;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    root = new node(0,N-1);
    for (int i = 0; i < N-1; i++) {
        if (K[i] > R) root->up(i);
    }
    fill(l,l+SZ,-1);
    fill(r,r+SZ,-1);
    iota(RR,RR+SZ,0);
    for (int i = 0; i < N; i++){
        up(i,1);
        pos.insert({i,-1});
    }
    for (int i = 0; i < C; i++){
        int cur = 0;
        int lo = 0, hi = N;
        while (lo < hi){
            int mid = (lo+hi)/2;
            if (sum(mid) < S[i]+1) lo = mid+1;
            else hi = mid;
        }
        l[i] = lo;
        lo = 0, hi = N;
        while (lo < hi){
            int mid = (lo+hi)/2;
            if (sum(mid) < E[i]+1) lo = mid+1;
            else hi = mid;
        }
        r[i] = RR[lo];
        //printf("tourney %d covers <%d,%d>\n",i,l[i],r[i]);
        if (l[i] == N) return 1;
        auto it = pos.lower_bound({l[i],-1});
        while (it != pos.end() && it->first <= r[i]){
            up(it->first,-1);
            it = pos.erase(it);
        }
        RR[l[i]] = r[i];
        pos.insert({l[i],i});
        up(l[i],1);
    }
    for (int i = 0; i < C; i++){
        if (!root->query(l[i],r[i]-1)){
            //printf("updating %d %d\n",l[i],r[i]);
            a[l[i]]++;
            a[r[i]+1]--;
        }
    }
    int ans = 0;
    for (int i = 1; i < N; i++){
        a[i] += a[i-1];
        if (a[i] > a[ans]) {
            //printf("%d %d\n",i,a[i]);
            ans = i;
        }
    }
    return ans;

}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:67:13: warning: unused variable 'cur' [-Wunused-variable]
         int cur = 0;
             ^~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 6 ms 1536 KB Output is correct
3 Correct 6 ms 1664 KB Output is correct
4 Correct 6 ms 1536 KB Output is correct
5 Correct 5 ms 1536 KB Output is correct
6 Correct 6 ms 1664 KB Output is correct
7 Correct 6 ms 1640 KB Output is correct
8 Correct 6 ms 1664 KB Output is correct
9 Correct 6 ms 1536 KB Output is correct
10 Correct 6 ms 1664 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1664 KB Output is correct
2 Correct 12 ms 2304 KB Output is correct
3 Correct 8 ms 2304 KB Output is correct
4 Correct 13 ms 2304 KB Output is correct
5 Correct 11 ms 2304 KB Output is correct
6 Correct 11 ms 2304 KB Output is correct
7 Correct 11 ms 2304 KB Output is correct
8 Correct 12 ms 2304 KB Output is correct
9 Correct 8 ms 2304 KB Output is correct
10 Correct 14 ms 2304 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 9464 KB Output is correct
2 Correct 166 ms 17528 KB Output is correct
3 Correct 70 ms 16760 KB Output is correct
4 Correct 165 ms 17528 KB Output is correct
5 Correct 153 ms 16888 KB Output is correct
6 Correct 198 ms 17272 KB Output is correct
7 Correct 159 ms 17528 KB Output is correct
8 Correct 161 ms 17528 KB Output is correct
9 Correct 72 ms 16888 KB Output is correct
10 Correct 85 ms 16832 KB Output is correct