oj.uz

답안 #242362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242362 2020-06-27T09:58:31 Z tqbfjotld 마상시합 토너먼트 (IOI12_tournament) C++14
100 / 100
 342 ms 36856 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

pair<int,int> actual[100005];

bool cmp(pair<int,int> a, pair<int,int> b){
    if (a.first==b.first) return a.second>b.second;
    return a.first<b.first;
}
vector<int> adjl[100005];
int ranks[100005];
int k;

struct nd{
    int s,e,v;
    nd *l,*r;
    nd(int _s, int _e){
        s = _s;
        e = _e;
        if (s==e){
            v = ranks[s];
        }
        else{
            l = new nd(s,(s+e)/2);
            r = new nd((s+e)/2+1,e);
            v = max(l->v,r->v);
            //printf("v %d %d = %d\n",s,e,v);
        }
    }
    int query(int a, int b){
        if (a<=s && e<=b) return v;
        if (b<=(s+e)/2) return l->query(a,b);
        if (a>(s+e)/2) return r->query(a,b);
        return max(l->query(a,b),r->query(a,b));
    }
}*root;

pair<int,int> dfs(int node, int dist){
    int mx = root->query(actual[node].first,actual[node].second-1);
    //printf("querying %d %d\n",actual[node].first,actual[node].second-1);
    //printf("node %d, mx %d\n",node,mx);
    if (mx>k){
        dist = 0;
    }
    int nd = -1;
    pair<int,int> ans = {-1,-1};
    int r = actual[node].first-1;
    for (auto x : adjl[node]){
        if (nd==-1 && actual[x].first>r+1){
            nd = r+1;
        }
        auto res = dfs(x,dist+1);
        if (res.first>ans.first || (res.first==ans.first && res.second<ans.second)){
            ans = res;
        }
    }
    if (nd==-1 && r<actual[node].second){
        nd = r+1;
    }
    if (nd!=-1){
        if (dist>ans.first || (ans.first==dist && nd<ans.second)){
            ans = {dist,nd};
        }
    }
    return ans;
}



using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    k = R;
    for (int x = 0; x<N-1; x++){
        ranks[x] = K[x];
        //printf("ranks %d = %d\n",x,K[x]);
    }
    root = new nd(0,N-2);
    indexed_set pb;
    for (int x = 0; x<=2*N; x++){
        pb.insert(x);
    }
    //printf("%d\n",root->query(0,1));
    for (int x = 0; x<C; x++){
        actual[x] = {*pb.find_by_order(S[x]),*pb.find_by_order(E[x]+1)-1};
        auto en = pb.find_by_order(E[x]+1);
        for (auto it = pb.find_by_order(S[x]+1); ; ){

            if ((*it)==actual[x].second+1) break;
            it = pb.erase(it);
        }
        assert(actual[x].second<N);
    }
    sort(actual,actual+C,cmp);
    //return 0;
    assert(actual[0]==make_pair(0,N-1));
    stack<int> st;
    st.push(0);
    for (int x = 1; x<C; x++){
        while (actual[x].second>actual[st.top()].second){
            assert(!st.empty());
            st.pop();
        }
        if (actual[x].second<=actual[st.top()].second){
            adjl[st.top()].push_back(x);
            st.push(x);
        }
    }

    return dfs(0,R==N-1?1:0).second;

}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:89:14: warning: variable 'en' set but not used [-Wunused-but-set-variable]
         auto en = pb.find_by_order(E[x]+1);
              ^~

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2944 KB Output is correct
2 Correct 15 ms 4480 KB Output is correct
3 Correct 12 ms 3840 KB Output is correct
4 Correct 14 ms 4096 KB Output is correct
5 Correct 14 ms 4096 KB Output is correct
6 Correct 14 ms 3968 KB Output is correct
7 Correct 15 ms 4224 KB Output is correct
8 Correct 14 ms 4224 KB Output is correct
9 Correct 11 ms 3840 KB Output is correct
10 Correct 16 ms 3968 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 14712 KB Output is correct
2 Correct 330 ms 36856 KB Output is correct
3 Correct 259 ms 25640 KB Output is correct
4 Correct 302 ms 30968 KB Output is correct
5 Correct 312 ms 32216 KB Output is correct
6 Correct 342 ms 26488 KB Output is correct
7 Correct 304 ms 32888 KB Output is correct
8 Correct 327 ms 33016 KB Output is correct
9 Correct 232 ms 25336 KB Output is correct
10 Correct 235 ms 25592 KB Output is correct