oj.uz

Submission #583683

# Submission time Handle Problem Language Result Execution time Memory
583683 2022-06-26T04:29:09 Z hibiki Jousting tournament (IOI12_tournament) C++11
100 / 100
 163 ms 20368 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n,c,r;
vector<int> as[100005],rs[100005];
int rmq[100005][20];

int get_max(int l, int r)
{
    int j = log2(r - l);
    return max(rmq[l][j], rmq[r - (1<<j)][j]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    n = N, c = C, r = R;
    indexed_set<int> os;
    for(int i = 0; i < n - 1; i++)
        rmq[i][0] = K[i];
    for(int j = 1; j < 20; j++)
        for(int i = 0; i + (1<<j) - 1 < n; i++)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j - 1))][j - 1]);
    for(int i = 0; i <= n; i++)
        os.insert(i);
    for(int i = 0; i < c; i++)
    {
        int st = *os.find_by_order(S[i]);
        int ed = *os.find_by_order(E[i] + 1) - 1;

        for(int j = S[i] + 1; j <= E[i]; j++)
            os.erase(os.find_by_order(S[i] + 1));

        S[i] = st, E[i] = ed;
    }
    for(int i = 0; i < c; i++)
    {
        as[S[i]].pb(i);
        rs[E[i] + 1].pb(i);
    }
    int cnt = 0, ans = 0, po;
    for(int i = 0; i < n; i++)
    {
        for(auto j: rs[i])
        {
            // printf("%d %d %d\n",S[j],E[j],get_max(S[j], E[j]));
            if(get_max(S[j], E[j]) < r)
                cnt--;
        }
        for(auto j: as[i])
        {
            // printf("%d %d %d\n",S[j],E[j],get_max(S[j], E[j]));
            if(get_max(S[j], E[j]) < r)
                cnt++;
        }

        if(cnt > ans)
        {
            ans = cnt;
            po = i;
        }
        // printf("%d\n",ans);
    }
    return po;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:73:12: warning: 'po' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     return po;
      |            ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5012 KB Output is correct
7 Correct 3 ms 5016 KB Output is correct
8 Correct 3 ms 5092 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 5 ms 5076 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 7 ms 5660 KB Output is correct
3 Correct 6 ms 5660 KB Output is correct
4 Correct 7 ms 5716 KB Output is correct
5 Correct 6 ms 5716 KB Output is correct
6 Correct 7 ms 5768 KB Output is correct
7 Correct 7 ms 5716 KB Output is correct
8 Correct 8 ms 5716 KB Output is correct
9 Correct 6 ms 5588 KB Output is correct
10 Correct 9 ms 5788 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 11752 KB Output is correct
2 Correct 134 ms 20360 KB Output is correct
3 Correct 92 ms 18624 KB Output is correct
4 Correct 123 ms 20304 KB Output is correct
5 Correct 121 ms 19660 KB Output is correct
6 Correct 163 ms 19656 KB Output is correct
7 Correct 127 ms 20312 KB Output is correct
8 Correct 127 ms 20368 KB Output is correct
9 Correct 82 ms 18460 KB Output is correct
10 Correct 99 ms 18608 KB Output is correct