Submission #655447

#	Time	Username	Problem	Language	Result	Execution time	Memory
655447		Ronin13	Jousting tournament (IOI12_tournament)	C++14	100 / 100	323 ms	31868 KiB

tournament

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

/*
5 3 3
1 0 2 4
1 3
0 1
0 1
*/
const int NMAX = 2e5 + 1;
vector <int> t(4 * NMAX), lazy1(4 * NMAX), lazy2(4 * NMAX);

void push1(int v){
    if(lazy1[v]){
        t[2 * v] += lazy1[v];
        t[2 * v + 1] += lazy1[v];
        lazy1[2 * v] += lazy1[v];
        lazy1[2 * v + 1] += lazy1[v];
        lazy2[2 * v] = lazy2[2 * v + 1] = lazy1[v] = 0;
    }
}

void push2(int v){
    if(lazy2[v]){
        t[2 * v] = t[2 * v + 1] = lazy2[2 * v] = lazy2[2 * v + 1] = lazy2[v];
        lazy2[v] = lazy1[2 * v] = lazy1[2 * v + 1] = 0;
    }
}

int getfirst(int v, int l, int r, int val){
    if(l == r){
        if(t[v] < val) return -1;
        return l;
    }
    push1(v);
    push2(v);
    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);
}

void update1(int v, int l, int r, int st, int fin, int val){
    if(l > fin || r < st) return;
    if(l >= st && r <= fin){
        lazy1[v] += val;
        t[v] += val;
        return;
    }
    push1(v);
    push2(v);
    int m = (l + r) / 2;
    update1(2 * v, l, m, st, fin, val);
    update1(2 * v + 1, m + 1, r, st, fin, val);
    t[v] = max(t[2 * v], t[2 * v+ 1]);
}

void update2(int v, int l, int r, int st, int fin, int val){
    if(l > fin || r < st) return;
    if(l >= st && r <= fin){
        lazy1[v] = val;
        t[v] = val;
        return;
    }
    push1(v);
    push2(v);
    int m = (l + r) / 2;
    update2(2 * v, l, m, st, fin, val);
    update2(2 * v + 1, m + 1, r, st, fin, val);
    t[v] = max(t[2 * v], t[2 * v+ 1]);
}

void build(int v, int l, int r){
    if(l == r){
        t[v] = l;
        return;
    }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

vector <int> p(NMAX), sz(NMAX);

void make_set(int v){
    p[v] = v;
    sz[v] = 1;
    return;
}

int find_set(int v){
    if(p[v] == v) return v;
    return p[v] = find_set(p[v]);
}

void union_sets(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
}

vector <int> bit(NMAX);

int lsb(int x){
    return x & -x;
}

void add(int pos, int val){
    while(pos < NMAX){
        bit[pos] += val;
        pos += lsb(pos);
    }
}

int get(int pos){
    int res = 0;
    while(pos){
        res += bit[pos];
        pos -= lsb(pos);
    }
    return res;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    set <int> st;
    for(int i = 0; i < N - 1; i++){
        if(K[i] > R) st.insert(i);
    }
    vector <pii> vec;
    vector <int> ans(N + 1, 1e9);
    for(int i = 1; i <= N; i++){
        auto it = st.upper_bound(i - 2);
        if(it != st.end()) vec.pb({i, *it + 2});
        if(it != st.begin()){
            it--;
            vec.pb({i, *it + 1});
        }
    }
    /*for(auto to : vec){
        cout << to.f << ' ' << to.s << "\n";
    }*/
    int n = N;
    build(1, 1, n);
    vector <vector <int> > qv;
    for(int i = 0; i < C; i++){
        int x = S[i], y = E[i];
        x++, y++;
        vector <int> cur;
        for(int i = x; i <= y; i++){
            int v = getfirst(1, 1, n, i);
            cur.pb(v);
        }

        int v = getfirst(1, 1, n, y + 1);
        if(v == -1){
            update2(1,1 , n, cur[0], n, x);
            S[i] = cur[0];
            E[i] = n;
        }
        else{
            update2(1, 1, n, cur[0], v - 1, x);
            update1(1, 1, n, v, n, x - y);
            S[i] = cur[0];
            E[i] = v - 1;
        }
        qv.pb(cur);
    }
    /*for(int i = 0; i < C; i++){
        for(int to : qv[i]){
            cout << to << ' ';
        }
        cout << "\n";
    }*/
    vector <int> l(vec.size(), -1), r(vec.size(), C);
    for(int j = 0; j < 18; j++){
        vector <vector <int> > mid(n + 1);
        for(int i = 0; i < vec.size(); i++){
            int m = l[i] + r[i];
            if(l[i] + 1 == r[i]) continue;
            mid[m / 2].pb(i);
        }
        for(int i = 1; i<= n; i++) make_set(i);
        for(int i = 0; i < C; i++){
            for(int k = 1; k < qv[i].size(); k++) union_sets(qv[i][k], qv[i][k - 1]);
            for(int to : mid[i]){
                int x = vec[to].f, y = vec[to].s;
                if(find_set(x) == find_set(y)) {
                    r[to] = i;
                }
                else l[to] = i;
            }
        }
    }
    for(int i = 0; i < vec.size(); i++){
        auto to = vec[i].f;
        ans[to] = min(ans[to], r[i]);
      // cout << r[i] << ' ';
    }
    //cout << "\n";
    vector <vector <int>  > vv(C);
    for(int i = 1; i <= n; i++){
        //cout << ans[i] << ' ';
        if(ans[i] && ans[i] <= C)vv[ans[i] - 1].pb(i);
    }
    int aa[n + 1];
    fill(aa + 1, aa + n + 1, 0);
    for(int i = 0; i < C; i++){
        add(S[i], 1);
        add(E[i] + 1, -1);
        for(int to : vv[i])
            aa[to] = get(to);
    }
    int mx = -1, mxi;
    for(int i = 1; i <= n; i++){
       // cout << aa[i] << " ";
        if(aa[i] > mx)
            mx = aa[i], mxi = i;
    }
    return mxi - 1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:189:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |         for(int i = 0; i < vec.size(); i++){
      |                        ~~^~~~~~~~~~~~
tournament.cpp:196:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |             for(int k = 1; k < qv[i].size(); k++) union_sets(qv[i][k], qv[i][k - 1]);
      |                            ~~^~~~~~~~~~~~~~
tournament.cpp:206:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
tournament.cpp:231:18: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  231 |     return mxi - 1;
      |                  ^

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