Submission #202236

# Submission time Handle Problem Language Result Execution time Memory
202236 2020-02-14T11:13:48 Z anonymous Teams (IOI15_teams) C++14
13 / 100
1682 ms 147424 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 {
            if (S.back().h < K[i] - 1) {S.back().v = 0;}
            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) { //merge ranges
                        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 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 248 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 380 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 5 ms 248 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 82 ms 28396 KB Output is correct
2 Correct 86 ms 28524 KB Output is correct
3 Correct 84 ms 28384 KB Output is correct
4 Correct 85 ms 28780 KB Output is correct
5 Correct 47 ms 25840 KB Output is correct
6 Correct 46 ms 25836 KB Output is correct
7 Correct 46 ms 25964 KB Output is correct
8 Correct 48 ms 25836 KB Output is correct
9 Correct 58 ms 25836 KB Output is correct
10 Correct 50 ms 25836 KB Output is correct
11 Correct 40 ms 25836 KB Output is correct
12 Correct 41 ms 25836 KB Output is correct
13 Correct 53 ms 26220 KB Output is correct
14 Correct 56 ms 26860 KB Output is correct
15 Correct 72 ms 28012 KB Output is correct
16 Correct 73 ms 28012 KB Output is correct
17 Correct 45 ms 25836 KB Output is correct
18 Correct 45 ms 25964 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 86 ms 28780 KB Output is correct
2 Correct 94 ms 28912 KB Output is correct
3 Correct 371 ms 31724 KB Output is correct
4 Correct 85 ms 28780 KB Output is correct
5 Correct 137 ms 26080 KB Output is correct
6 Correct 128 ms 26092 KB Output is correct
7 Correct 53 ms 26092 KB Output is correct
8 Correct 109 ms 26092 KB Output is correct
9 Correct 58 ms 25836 KB Output is correct
10 Correct 97 ms 26220 KB Output is correct
11 Correct 110 ms 26220 KB Output is correct
12 Correct 194 ms 26220 KB Output is correct
13 Correct 338 ms 26732 KB Output is correct
14 Correct 487 ms 29804 KB Output is correct
15 Incorrect 179 ms 28652 KB Output isn't correct
16 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 594 ms 141640 KB Output is correct
2 Correct 557 ms 141536 KB Output is correct
3 Correct 1416 ms 147424 KB Output is correct
4 Correct 547 ms 141536 KB Output is correct
5 Correct 408 ms 128096 KB Output is correct
6 Correct 393 ms 128224 KB Output is correct
7 Correct 230 ms 128100 KB Output is correct
8 Correct 365 ms 128104 KB Output is correct
9 Correct 291 ms 128224 KB Output is correct
10 Correct 302 ms 128352 KB Output is correct
11 Correct 361 ms 128436 KB Output is correct
12 Correct 581 ms 128864 KB Output is correct
13 Correct 1108 ms 130912 KB Output is correct
14 Correct 1682 ms 142372 KB Output is correct
15 Incorrect 672 ms 138336 KB Output isn't correct
16 Halted 0 ms 0 KB -