oj.uz

Submission #223022

# Submission time Handle Problem Language Result Execution time Memory
223022 2020-04-14T13:44:37 Z jovan_b Jousting tournament (IOI12_tournament) C++17
100 / 100
 914 ms 19192 KB 
#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

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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5120 KB Output is correct
2 Correct 38 ms 5752 KB Output is correct
3 Correct 14 ms 5248 KB Output is correct
4 Correct 38 ms 5632 KB Output is correct
5 Correct 35 ms 5632 KB Output is correct
6 Correct 27 ms 5504 KB Output is correct
7 Correct 36 ms 5752 KB Output is correct
8 Correct 35 ms 5624 KB Output is correct
9 Correct 10 ms 5248 KB Output is correct
10 Correct 41 ms 5496 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 8696 KB Output is correct
2 Correct 901 ms 19192 KB Output is correct
3 Correct 99 ms 9208 KB Output is correct
4 Correct 865 ms 15996 KB Output is correct
5 Correct 914 ms 16888 KB Output is correct
6 Correct 615 ms 13816 KB Output is correct
7 Correct 875 ms 18808 KB Output is correct
8 Correct 876 ms 18552 KB Output is correct
9 Correct 46 ms 9472 KB Output is correct
10 Correct 99 ms 9852 KB Output is correct