Submission #223022

#	Time	Username	Problem	Language	Result	Execution time	Memory
223022		jovan_b	Jousting tournament (IOI12_tournament)	C++17	100 / 100	914 ms	19192 KiB

tournament

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;

using namespace __gnu_pbds;
using namespace std;

template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

int ts[100005], te[100005];

struct segment{
    int val;
    int lazy;
    int mx;
} seg[400005];

int n, nas;

int niz[100005];

void propagate(int node, int l, int r){
    if(!seg[node].lazy || !seg[node].val) return;
    seg[node].val = 0;
    if(l == r) return;
    seg[node*2].lazy = seg[node*2+1].lazy = 1;
}

void init(int node, int l, int r){
    seg[node].lazy = 0;
    if(l == r){
        seg[node].val = niz[l];
        seg[node].mx = niz[l];
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    seg[node].val = seg[node*2].val + seg[node*2+1].val;
    seg[node].mx = max(seg[node*2].mx, seg[node*2+1].mx);
}

int getsum(int node, int l, int r, int tl, int tr){
    propagate(node, l, r);
    if(tl > r || l > tr) return 0;
    if(tl <= l && r <= tr) return seg[node].val;
    int mid = (l+r)/2;
    return getsum(node*2, l, mid, tl, tr) + getsum(node*2+1, mid+1, r, tl, tr);
}

void flatten(int node, int l, int r, int tl, int tr){
    propagate(node, l, r);
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy = 1;
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    flatten(node*2, l, mid, tl, tr);
    flatten(node*2+1, mid+1, r, tl, tr);
    seg[node].val = seg[node*2].val + seg[node*2+1].val;
}

void updpoint(int node, int l, int r, int x, int val){
    if(l == r){
        seg[node].mx = val;
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) updpoint(node*2, l, mid, x, val);
    else updpoint(node*2+1, mid+1, r, x, val);
    seg[node].mx = max(seg[node*2].mx, seg[node*2+1].mx);
}

int getmax(int node, int l, int r, int tl, int tr){
    if(tl > r || l > tr) return 0;
    if(tl <= l && r <= tr) return seg[node].mx;
    int mid = (l+r)/2;
    return max(getmax(node*2, l, mid, tl, tr), getmax(node*2+1, mid+1, r, tl, tr));
}

int findnum(int x){
    /// najmanji veci jednak
    int l = 1, r = n, res = n;
    while(l <= r){
        int mid = (l+r)/2;
        int k = getsum(1, 1, n, 1, mid);
        if(k >= x){
            res = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    return res;
}

ordered_set <pair <int, ll>> q;

vector <int> vec[100005];
vector <int> nazad[100005];

int proveri(){
    return q.order_of_key({nas, 1e10+1});
}

ll hes(int a, int b){
    return 1e5*a+b;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

    int xx = clock();
    n = N, nas = R+1;
    for(int i=1; i<=n; i++) niz[i] = 1;
    init(1, 1, n);
    for(int i=0; i<C; i++){
        S[i]++;
        E[i]++;
        ts[i+1] = findnum(S[i]);
        int tkraj = findnum(E[i]);
        flatten(1, 1, N, ts[i+1]+1, tkraj);
    }
    init(1, 1, n);
    for(int i=0; i<C; i++){
        int tpoc = findnum(S[i]);
        te[i+1] = findnum(E[i]);
        flatten(1, 1, N, tpoc, te[i+1]-1);
    }
    for(int i=1; i<=C; i++){
        vec[ts[i]].push_back(te[i]);
        nazad[te[i]+1].push_back(ts[i]);
    }
    niz[1] = R+1;
    for(int i=2; i<=n; i++){
        niz[i] = K[i-2]+1;
    }
    int res = 0, tr = 1;
    init(1, 1, n);
    for(auto c : vec[1]) q.insert({getmax(1, 1, n, 1, c), hes(1, c)});
    res = max(res, proveri());
    for(int i=2; i<=n; i++){
        for(auto c : nazad[i]){
            q.erase({getmax(1, 1, n, c, i-1), hes(c, i-1)});
        }
        updpoint(1, 1, n, i, niz[i-1]);
        updpoint(1, 1, n, i-1, niz[i]);
        swap(niz[i-1], niz[i]);
        for(auto c : vec[i]){
            q.insert({getmax(1, 1, n, i, c), hes(i, c)});
        }
        //cout << q.size() << " " << i << endl;
        //cout << q.begin()->first << endl;
        int k = proveri();
        if(k > res){
            res = k;
            tr = i;
        }
    }
    return tr-1;
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/
/*
5 1 2
0 1 3 4
1 2
*/

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:117:9: warning: unused variable 'xx' [-Wunused-variable]
     int xx = clock();
         ^~

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