Submission #789573

#	Time	Username	Problem	Language	Result	Execution time	Memory
789573		Ronin13	Jousting tournament (IOI12_tournament)	C++17	0 / 100	66 ms	6444 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 <pii>  st;
    for(int i = 0; i <= n - 1; i++){
        st.insert({i, 0});
    }
    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;
    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});
        auto it2 = st.lower_bound({r, -1});
        vector <pii> vec;
        int mx = 0, mx1 = 0;
        while(it1 != it2){
            vec.pb(*it1);
            mx1 = max(mx1, (*it1).s);
            update(1, 0, n, (*it1).f, 0);
            it1++;
        }
       // r = vec.back().f;
        r--;
        //cout << l << ' ' << nx[l] << "\n";
        if(nx[l] > r - 1)
          ans = max(ans, mx1 + 1);
        update(1, 0, n, l, 1);
        for(auto to : vec)
          st.erase(to);
        st.insert({l, mx1 + 1});
    }
    return ans;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:65:13: warning: unused variable 'mx' [-Wunused-variable]
   65 |         int mx = 0, mx1 = 0;
      |             ^~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51