Submission #202235

# Submission time Handle Problem Language Result Execution time Memory
202235 2020-02-14T11:07:11 Z anonymous Teams (IOI15_teams) C++14
13 / 100
1761 ms 147552 KB
#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, h[i] are strictly decreasing
    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 { //newh <= prev h
                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;
                    if (S.size() > 1 && S[S.size()-2].h == S.back().h) {
                        S.pop_back();
                        S.back().r = K[i];
                    }
                }

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

Compilation message

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();
         ^
# Verdict Execution time Memory Grader output
1 Correct 7 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 7 ms 376 KB Output is correct
13 Correct 7 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 6 ms 376 KB Output is correct
18 Incorrect 5 ms 376 KB Output isn't correct
19 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 86 ms 28524 KB Output is correct
2 Correct 84 ms 28396 KB Output is correct
3 Correct 86 ms 28312 KB Output is correct
4 Correct 88 ms 28780 KB Output is correct
5 Correct 46 ms 25836 KB Output is correct
6 Correct 46 ms 25836 KB Output is correct
7 Correct 48 ms 25956 KB Output is correct
8 Correct 45 ms 25836 KB Output is correct
9 Correct 57 ms 25836 KB Output is correct
10 Correct 49 ms 25836 KB Output is correct
11 Correct 41 ms 25836 KB Output is correct
12 Correct 40 ms 25964 KB Output is correct
13 Correct 54 ms 26220 KB Output is correct
14 Correct 54 ms 26988 KB Output is correct
15 Correct 73 ms 28012 KB Output is correct
16 Correct 72 ms 28048 KB Output is correct
17 Correct 44 ms 25964 KB Output is correct
18 Correct 45 ms 25836 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 89 ms 28988 KB Output is correct
2 Correct 88 ms 28780 KB Output is correct
3 Correct 363 ms 31728 KB Output is correct
4 Correct 84 ms 28780 KB Output is correct
5 Correct 137 ms 26092 KB Output is correct
6 Correct 127 ms 26092 KB Output is correct
7 Correct 54 ms 26092 KB Output is correct
8 Correct 108 ms 26092 KB Output is correct
9 Correct 55 ms 25964 KB Output is correct
10 Correct 102 ms 26220 KB Output is correct
11 Correct 108 ms 26220 KB Output is correct
12 Correct 187 ms 26220 KB Output is correct
13 Correct 345 ms 26744 KB Output is correct
14 Correct 480 ms 29804 KB Output is correct
15 Incorrect 186 ms 28620 KB Output isn't correct
16 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 560 ms 141408 KB Output is correct
2 Correct 556 ms 141384 KB Output is correct
3 Correct 1439 ms 147552 KB Output is correct
4 Correct 539 ms 141408 KB Output is correct
5 Correct 418 ms 128224 KB Output is correct
6 Correct 394 ms 128096 KB Output is correct
7 Correct 230 ms 128096 KB Output is correct
8 Correct 364 ms 128096 KB Output is correct
9 Correct 294 ms 128352 KB Output is correct
10 Correct 304 ms 128352 KB Output is correct
11 Correct 367 ms 128356 KB Output is correct
12 Correct 553 ms 128664 KB Output is correct
13 Correct 1164 ms 130788 KB Output is correct
14 Correct 1761 ms 142176 KB Output is correct
15 Incorrect 685 ms 138340 KB Output isn't correct
16 Halted 0 ms 0 KB -