Submission #202234

#	Time	Username	Problem	Language	Result	Execution time	Memory
202234		anonymous	Teams (IOI15_teams)	C++14	13 / 100	1694 ms	147404 KiB

teams

#include "teams.h"
#include<vector>
#include<map>
#include<algorithm>
#define MAXN 500005
using namespace std;
class PersistentSegtree {
    int ST[MAXN*30][3]; //Sum, L, R
    int R[MAXN], pt=1, ver=1; //roots,  first unused node index & version
    map<int, int> P; //inserted points to first occurrence
public:
    int upd(int ind, int l, int r, int cur) { //cur is prev node for this range
        if (l > ind || ind > r) {return(cur);}
        int v = pt, mid=(l+r)>>1;
        pt++;
        if (l == r) {
            ST[v][0]=ST[cur][0]+1; //0 is dummy node
        } else {
            ST[v][1]=upd(ind, l, mid, ST[cur][1]);
            ST[v][2]=upd(ind, mid+1, r, ST[cur][2]);
            ST[v][0]=ST[ST[v][1]][0]+ST[ST[v][2]][0];
        }
        return(v);
    }
    int ask(int lo, int hi, int l, int r, int cur) { //range sum for certain version
        if (hi < l || lo > r || cur == 0) {return(0);}
        if (lo <= l && r <= hi) {return(ST[cur][0]);}
        else {
            int mid=(l+r)>>1;
            return(ask(lo, hi, l, mid, ST[cur][1])+
                   ask(lo, hi, mid+1, r, ST[cur][2]));
        }
    }
    int kth(int k, int l, int r, int cur1, int cur2) { //kth smallest: k is zero indexed cur1=l
        if (l == r) {return(l);}
        int mid=(l+r)>>1;
        if (ST[ST[cur2][1]][0]-ST[ST[cur1][1]][0] <= k) {
            return(kth(k-ST[ST[cur2][1]][0]+ST[ST[cur1][1]][0],
                       mid+1,r, ST[cur1][2],ST[cur2][2]));
        } else {
            return(kth(k,l,mid, ST[cur1][1],ST[cur2][1]));
        }
    }
    void add(int a, int b) { //A val & B val for student
        P[a]=ver;
        R[ver]=upd(b, 1, MAXN, R[ver-1]);
        ver++;
    }
    int kthelem(int k, int lo, int hi) {
        int ver1=(*(--P.lower_bound(lo))).second; //be careful
        int ver2=(*(--P.upper_bound(hi))).second;
        return(kth(k, 1, MAXN, R[ver1], R[ver2]));
    }
    int Sum(int loA, int hiA, int loB, int hiB) {
        int ver1=(*(--P.lower_bound(loA))).second;
        int ver2=(*(--P.upper_bound(hiA))).second;
        return(ask(loB, hiB, 1, MAXN, R[ver2])-
               ask(loB, hiB, 1, MAXN, R[ver1]));
    }
    void init() {P[-1<<30]=0;}
} PST;

vector<pair<int,int> > Students;
void init(int N, int A[], int B[]) {
    PST.init();
    for (int i=0; i<N; i++) {
        Students.push_back({A[i], B[i]});
    }
    sort(Students.begin(), Students.end());
    for (auto s: Students) {
        PST.add(s.first, s.second);
    }
}

struct range {
    int l, r, h, v; //left, right, height of bar. All students up to h inclusive in [l,r] inclusive has been taken
    //further v students on line y=h+1 have been taken
};


//observation: visualisation ranges of taken students on 2D as barchart the barchart is decreasing staircase
//use amortisation + kth order statistic to maintain staircase

int can(int M, int K[]) {
    int N=Students.size();
    vector <range> S; //stack of ranges
    sort(K, K+M);
    for (int i=0; i<M; i++) {
        while (S.size() && S.back().h < K[i]-1) {
            S.pop_back();
        }
        range New;
        if (S.size()) {New.l=S.back().r+1;}
        else {New.l=0;}
        New.r = K[i], New.h=K[i]-1, New.v=0;
        if (New.l <= New.r && (S.empty() || S.back().h != New.h)) {S.push_back(New);}
        else {S.back().h=max(S.back().h, K[i]-1), S.back().r=K[i];}
        int Need=K[i];
        while (S.size() > 1 && PST.Sum(S.back().l, S.back().r, S.back().h+1, S[S.size()-2].h)-S.back().v <= Need) {
            Need-=PST.Sum(S.back().l, S.back().r, S.back().h+1, S[S.size()-2].h)+S.back().v;
            S.pop_back();
            S.back().r=K[i];
        }
        if (Need != 0) {
            if (PST.Sum(S.back().l, S.back().r, S.back().h+1, MAXN) - S.back().v < Need) { //no more points to fill
                return(false);
            } else {
                int newh= PST.kthelem(Need+S.back().v-1 + PST.Sum(S.back().l, S.back().r, 0, S.back().h), S.back().l, S.back().r);
                if (PST.Sum(S.back().l, S.back().r, S.back().h+1, newh) - S.back().v > Need) {
                    S.back().v = Need - PST.Sum(S.back().l, S.back().r, S.back().h+1, newh-1) + S.back().v;
                    S.back().h = newh-1;
                } else {
                    S.back().h = newh;
                    S.back().v = 0;
                }

            } //minus 1 as zero index
        }
    }
    return(true);
}

Compilation message (stderr)

teams.cpp: In member function 'void PersistentSegtree::init()':
teams.cpp:60:24: warning: left shift of negative value [-Wshift-negative-value]
     void init() {P[-1<<30]=0;}
                        ^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:85:24: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     int N=Students.size();
           ~~~~~~~~~~~~~^~
teams.cpp:85:9: warning: unused variable 'N' [-Wunused-variable]
     int N=Students.size();
         ^

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