oj.uz

답안 #251188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251188 2020-07-20T14:02:41 Z eohomegrownapps 마상시합 토너먼트 (IOI12_tournament) C++14
100 / 100
 207 ms 17528 KB 
#include <bits/stdc++.h>
using namespace std;
#include <bits/extc++.h>
using namespace __gnu_pbds;

template <typename T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T, typename V>
using pbds_map = tree<T, V, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n,c;

int sparsetable[17][100000];
int lg2[100001];

void gentable(int *K){
    lg2[1]=0;
    for (int i = 2; i<=n; i++){
        lg2[i]=lg2[i/2]+1;
    }
    for (int i = 0; i<n-1; i++){
        sparsetable[0][i]=K[i];
    }
    sparsetable[0][n-1]=-1;
    for (int i = 1; (1<<i)<=n; i++){
        for (int x = 0; x+(1<<i)<=n; x++){
            sparsetable[i][x]=max(sparsetable[i-1][x],sparsetable[i-1][x+(1<<(i-1))]);
        }
    }
}

int rmq(int a, int b){
    int l2 = lg2[b-a+1];
    return max(sparsetable[l2][a],sparsetable[l2][b-(1<<l2)+1]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;c=C;
    vector<pair<int,int>> pos(n);
    for (int i = 0; i<n; i++){
        pos[i]={i,i};
    }
    pbds_set<pair<int,int>> items(pos.begin(), pos.end());
    vector<pair<int,bool>> ranges; //false -- add, true -- remove
    gentable(K);
    for (int i = 0; i<c; i++){
        auto its = items.find_by_order(S[i]);
        auto ite = items.find_by_order(E[i]);
        int a = its->first;
        int b = ite->second;
        //cout<<"rmq "<<a<<" "<<b-1<<" "<<rmq(a,b-1)<<'\n';
        if (rmq(a,b-1)<R){
            //cout<<"range "<<a<<" "<<b<<'\n';
            ranges.push_back({a, false});
            ranges.push_back({b, true});
        }
        //ranges[i]={its->first,ite->second};
        for (int j = 0; j<E[i]-S[i]+1; j++){
            its = items.erase(its);
        }
        items.insert({a,b});
        /*for (auto i : items){
            cout<<i.first<<" "<<i.second<<", ";
        }cout<<'\n';*/
    }
    /*for (auto i : ranges){
        cout<<i.first<<" "<<i.second<<'\n';
    }*/
    /*for (int i = 0; i<100; i++){
        int a,b;
        cin>>a>>b;
        cout<<rmq(a,b)<<'\n';
    }*/
    sort(ranges.begin(), ranges.end());
    int maxnum = 0;
    int maxind = 0;
    int curval = 0;
    for (auto p : ranges){
        if (p.second){
            curval--;
        } else {
            curval++;
        }
        if (curval>maxnum){
            maxnum=curval;
            maxind=p.first;
        }
    }
    //cout<<maxnum<<'\n';
    return maxind;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 8820 KB Output is correct
2 Correct 204 ms 17272 KB Output is correct
3 Correct 113 ms 15224 KB Output is correct
4 Correct 178 ms 17268 KB Output is correct
5 Correct 197 ms 16756 KB Output is correct
6 Correct 207 ms 17264 KB Output is correct
7 Correct 186 ms 17528 KB Output is correct
8 Correct 188 ms 17272 KB Output is correct
9 Correct 87 ms 14968 KB Output is correct
10 Correct 113 ms 15048 KB Output is correct