oj.uz

Submission #789636

# Submission time Handle Problem Language Result Execution time Memory
789636 2023-07-21T15:30:35 Z Ronin13 Jousting tournament (IOI12_tournament) C++17
100 / 100
 146 ms 12816 KB 
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
 
const int nmax = 200001;
 
vector <int> t(4 * nmax);
 
void update(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos)
      return;
    if(l == r){
      t[v] = val;
      return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v+ 1, m + 1, r, pos, val);
    t[v] = t[2 * v] + t[2 * v + 1];
}
 
int getfirst(int v, int l, int r, int val){
    if(l == r){
      return l;
    }
    int m = (l + r) / 2;
    if(t[2 * v] >= val)
      return getfirst(2 * v, l, m, val);
    return getfirst(2 *v  + 1, m + 1, r, val - t[2 * v]);
}
 
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
    for(int i = 0; i < n; i++){
        update(1, 0, n, i, 1);
    }
    update(1, 0, n, n, 1);
    set <pair<int, pii> >  st;
    for(int i = 0; i <= n - 1; i++){
        st.insert({i, {0, i}});
    }
    int nx[n + 1];
    int last = n - 1;
    nx[n - 1] = n - 1;
    for(int i = n - 2; i >= 0; i--){
        if(k[i] > r) last = i;
        nx[i] = last;
    }
    int ans = 0;
    int ansi = 0;
    for(int i = 0; i < c; i++){
        int x = s[i], y = e[i];
       
        int l = getfirst(1, 0, n, x + 1);
        int r = getfirst(1, 0, n, y + 2);
        
        auto it1 = st.lower_bound({l, {-1, -1}});
        auto it2 = st.lower_bound({r, {-1, -1}});
        vector <pair<int, pii> > vec;
        int mx1 = -1;
        int mxi;
        while(it1 != it2){
            vec.pb(*it1);
            if(mx1 < (*it1).s.f)
            mx1 = (*it1).s.f, mxi = (*it1).s.s;
            
            update(1, 0, n, (*it1).f, 0);
            it1++;
        }
       // r = vec.back().f;
        r--;
        if(nx[l] > r - 1){
        if(ans < mx1 + 1)
          ans = mx1 + 1, ansi = mxi;
      else if(ans == mx1 + 1) ansi = min(mxi,ansi);
        }
        update(1, 0, n, l, 1);
        for(auto to : vec)
          st.erase(to);
        st.insert({l, {mx1 + 1, mxi}});
    }
    return ansi;
}

Compilation message

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

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 7 ms 3796 KB Output is correct
3 Correct 4 ms 3840 KB Output is correct
4 Correct 6 ms 3848 KB Output is correct
5 Correct 6 ms 3776 KB Output is correct
6 Correct 7 ms 3796 KB Output is correct
7 Correct 6 ms 3796 KB Output is correct
8 Correct 6 ms 3780 KB Output is correct
9 Correct 4 ms 3924 KB Output is correct
10 Correct 9 ms 3796 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 7212 KB Output is correct
2 Correct 128 ms 12748 KB Output is correct
3 Correct 81 ms 12704 KB Output is correct
4 Correct 120 ms 12780 KB Output is correct
5 Correct 125 ms 12520 KB Output is correct
6 Correct 146 ms 12100 KB Output is correct
7 Correct 124 ms 12792 KB Output is correct
8 Correct 128 ms 12816 KB Output is correct
9 Correct 59 ms 12724 KB Output is correct
10 Correct 65 ms 11084 KB Output is correct