Submission #789636

#	Time	Username	Problem	Language	Result	Execution time	Memory
789636		Ronin13	Jousting tournament (IOI12_tournament)	C++17	100 / 100	146 ms	12816 KiB

tournament

#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 (stderr)

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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51