oj.uz

Submission #442043

# Submission time Handle Problem Language Result Execution time Memory
442043 2021-07-06T20:48:22 Z JovanB Jousting tournament (IOI12_tournament) C++17
49 / 100
 1000 ms 20740 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)});
        }
        int k = proveri();
        if(k > res){
            res = k;
            tr = i;
        }
    }
    return tr-1;
}

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 5 ms 4940 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 6 ms 5004 KB Output is correct
7 Correct 6 ms 5044 KB Output is correct
8 Correct 6 ms 5068 KB Output is correct
9 Correct 4 ms 5004 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5068 KB Output is correct
2 Correct 33 ms 5700 KB Output is correct
3 Correct 7 ms 5196 KB Output is correct
4 Correct 33 ms 5620 KB Output is correct
5 Correct 32 ms 5608 KB Output is correct
6 Correct 28 ms 5396 KB Output is correct
7 Correct 33 ms 5712 KB Output is correct
8 Correct 33 ms 5564 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 36 ms 5540 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 9324 KB Output is correct
2 Correct 967 ms 20740 KB Output is correct
3 Correct 108 ms 9956 KB Output is correct
4 Correct 968 ms 17480 KB Output is correct
5 Execution timed out 1091 ms 18272 KB Time limit exceeded
6 Halted 0 ms 0 KB -