Submission #367560

#	Time	Username	Problem	Language	Result	Execution time	Memory
367560		BartolM	Teams (IOI15_teams)	C++17	100 / 100	2530 ms	377852 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int MAXN=5e5+5;

struct Node{
    int val;
    Node *l, *r;
    Node(int val_=0, Node *l_=NULL, Node *r_=NULL) {
        val=val_; l=l_; r=r_;
    }
};

int n, OFF=1, m;
pii p[MAXN];
int zad[MAXN], que[MAXN];
Node *T[MAXN];
int dp[MAXN];
set <pii> S, Sind;

Node* build(int d) {
    if (d==0) return NULL;
    Node *ret=new Node(0, build(d/2), build(d/2));
    return ret;
}

Node* update(int ind, int x, Node* pos, int lo, int hi) {
    Node *ret=new Node(pos->val+x, pos->l, pos->r);
    if (lo==hi-1) return ret;

    int mid=(lo+hi)/2;
    if (ind<mid) ret->l=update(ind, x, pos->l, lo, mid);
    else ret->r=update(ind, x, pos->r, mid, hi);

    return ret;
}

int query(Node *lef, Node *rig, int a, int b, int lo, int hi) {
    if (lo>=b || hi<=a) return 0;
    if (lo>=a && hi<=b) return rig->val-lef->val;
    int mid=(lo+hi)/2;
    return query(lef->l, rig->l, a, b, lo, mid)+query(lef->r, rig->r, a, b, mid, hi);
}

int nadji(Node *lef, Node *rig, int x, int lo, int hi) {
    if (lo==hi-1) return lo;
    int mid=(lo+hi)/2;
    int des=rig->r->val-lef->r->val;
    if (des>=x) return nadji(lef->r, rig->r, x, mid, hi);
    return nadji(lef->l, rig->l, x-des, lo, mid);
}

#define DEBUG 0

void init(int N, int A[], int B[]) {
    n=N;
    for (int i=1; i<=n; ++i) p[i]=mp(A[i-1], B[i-1]);
    sort(p+1, p+n+1);

    while (OFF<n) OFF*=2;

    T[0]=build(OFF);
    for (int i=1; i<=n; ++i) {
        zad[p[i].X]=i;
        T[i]=update(p[i].Y, 1, T[i-1], 0, OFF);
//        printf("tournament: %d, updejtam broj %d\n", i, p[i].Y);
    }
    for (int i=1; i<=n; ++i) if (!zad[i]) zad[i]=zad[i-1];
}

int f(int lo, int hi, int i, int j) {
    int mid;
    while (lo<hi) {
        mid=(lo+hi+1)/2;
        int val_i=dp[i]+query(T[zad[que[i]]], T[zad[que[mid]]], que[mid], n+1, 0, OFF);
        int val_j=dp[j]+query(T[zad[que[j]]], T[zad[que[mid]]], que[mid], n+1, 0, OFF);
        if (val_i<val_j) lo=mid;
        else hi=mid-1;
    }
    return lo+1;
}

void izbaci(pii pp) {
//    printf("izbacujem %d\n", pp.Y);
    S.erase(pp);

    auto it=Sind.find(mp(pp.Y, pp.X));
    auto pr=it, nx=it; pr--; nx++;
    Sind.erase(it);

    if (nx==Sind.end()) return;
    pii pom=*nx;

//    printf("mijenjam granicu na indexu %d iz %d u ", pom.X, pom.Y);

    Sind.erase(nx);
    S.erase(mp(pom.Y, pom.X));

    pom.Y=f(pom.X, m, pom.X, pr->X);
//    printf("%d\n", pom.Y);

    Sind.insert(pom);
    S.insert(mp(pom.Y, pom.X));
}

int can(int M, int K[]) {

    m=M;
    sort(K, K+M);
    for (int i=0; i<M; ++i) que[i+1]=K[i];

    S.clear();
    Sind.clear();
    que[0]=0;
    dp[0]=0;
    S.insert(mp(M+2, 0));
    Sind.insert(mp(0, M+2));

    for (int i=1; i<=M; ++i) {
        while (S.begin()->X<=i) izbaci(*S.begin());
        assert(!S.empty());

        dp[i]=dp[Sind.rbegin()->X]+query(T[zad[que[Sind.rbegin()->X]]], T[zad[que[i]]], que[i], n+1, 0, OFF)-que[i];
        #if DEBUG
            printf("i: %d, que: %d, dp: %d, prijelaz: %d\n", i, que[i], dp[i], Sind.rbegin()->X);
        #endif // DEBUG
        if (dp[i]<0) return 0;
//        int br=dp[i]-dp[v.back().X];

        int curr=f(i, M, i, Sind.rbegin()->X);

        #if DEBUG
            printf("i: %d, prosli: %d, granica: %d\n", i, Sind.rbegin()->X, curr);
        #endif // DEBUG
        Sind.insert(mp(i, curr));
        S.insert(mp(curr, i));


//        dp[i]=INF;
//        for (int j=0; j<i; ++j) {
//            dp[i]=min(dp[i], dp[j]+query(T[zad[que[j]]], T[zad[que[i]]], que[i], n+1, 0, OFF)-que[i]);
//        }
//        if (dp[i]<0) return 0;
    }
    return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23