제출 #442043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442043		JovanB	마상시합 토너먼트 (IOI12_tournament)	C++17	49 / 100	1091 ms	20740 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)});
        }
        int k = proveri();
        if(k > res){
            res = k;
            tr = i;
        }
    }
    return tr-1;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51