제출 #979318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979318		LOLOLO	마상시합 토너먼트 (IOI12_tournament)	C++17	0 / 100	17 ms	5200 KiB

tournament

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e5 + 10;

vector <int> save[N];

struct fen{
    vector <ll> f;
    int N;
    void ass(int n) {
        N = n;
        f.assign(N + 1, 0);
    }

    void upd(int i, ll x) {
        for (; i; i -= i & (-i))
            f[i] += x;
    }

    ll get(int i) {
        ll s = 0;
        for (; i <= N; i += i & (-i))
            s += f[i];

        return s;
    }
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {    
    int n = N;
    int c = C;
    int r = R;

    for (int i = 0; i < c; i++) {
        S[i]++;
        E[i] += 2;
    }

    set <int> pos;
    for (int i = 1; i <= n; i++) {
        if (K[i - 1] > r) {
            pos.insert(i);
        }
    }

    pos.insert(n + 1);
    for (int i = 0; i < c; i++) {
        auto it = pos.lower_bound(S[i]);
        E[i] = min(E[i], *it); 
        save[S[i]].pb(E[i]);
    }

    fen f1, f2;
    f1.ass(n + 10);
    f2.ass(n + 10);

    priority_queue <int, vector <int>, greater <int>> pq;

    ll ans = 0, p = 0;
    for (ll i = 1; i <= n; i++) {
        for (auto x : save[i]) {
            pq.push(x);
            f1.upd(x, 1);
            f2.upd(x, x);
        }

        while (sz(pq) && pq.top() <= i) {
            int t = pq.top();
            f1.upd(t, -1);
            f2.upd(t, -t);
            pq.pop();
        }

        ll v = f2.get(i) - f1.get(i) * i;
        if (ans < v) {
            ans = v;
            p = i - 1;
        }
    }

    return p;
}


// 2 2
// 1 2

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