답안 #202234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202234 2020-02-14T10:57:22 Z anonymous 팀들 (IOI15_teams) C++14
13 / 100
1694 ms 147404 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
    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

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();
         ^
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 252 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 5 ms 376 KB Output is correct
8 Correct 5 ms 248 KB Output is correct
9 Correct 6 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 6 ms 376 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 6 ms 380 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 380 KB Output isn't correct
19 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 28396 KB Output is correct
2 Correct 87 ms 28396 KB Output is correct
3 Correct 93 ms 28396 KB Output is correct
4 Correct 85 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 45 ms 25836 KB Output is correct
8 Correct 50 ms 25836 KB Output is correct
9 Correct 57 ms 25964 KB Output is correct
10 Correct 48 ms 25836 KB Output is correct
11 Correct 39 ms 25836 KB Output is correct
12 Correct 39 ms 25836 KB Output is correct
13 Correct 52 ms 26220 KB Output is correct
14 Correct 52 ms 26864 KB Output is correct
15 Correct 72 ms 28012 KB Output is correct
16 Correct 72 ms 28012 KB Output is correct
17 Correct 47 ms 25836 KB Output is correct
18 Correct 45 ms 25836 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 28780 KB Output is correct
2 Correct 89 ms 28780 KB Output is correct
3 Correct 379 ms 31852 KB Output is correct
4 Correct 81 ms 28908 KB Output is correct
5 Correct 135 ms 26068 KB Output is correct
6 Correct 130 ms 26104 KB Output is correct
7 Correct 54 ms 26092 KB Output is correct
8 Correct 107 ms 26092 KB Output is correct
9 Correct 57 ms 25836 KB Output is correct
10 Correct 99 ms 26092 KB Output is correct
11 Correct 109 ms 26220 KB Output is correct
12 Correct 188 ms 26220 KB Output is correct
13 Correct 337 ms 26732 KB Output is correct
14 Correct 474 ms 29804 KB Output is correct
15 Incorrect 173 ms 28524 KB Output isn't correct
16 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 570 ms 141396 KB Output is correct
2 Correct 556 ms 141408 KB Output is correct
3 Correct 1413 ms 147404 KB Output is correct
4 Correct 542 ms 141408 KB Output is correct
5 Correct 417 ms 128096 KB Output is correct
6 Correct 397 ms 128200 KB Output is correct
7 Correct 228 ms 128096 KB Output is correct
8 Correct 370 ms 128120 KB Output is correct
9 Correct 290 ms 128224 KB Output is correct
10 Correct 302 ms 128364 KB Output is correct
11 Correct 357 ms 128352 KB Output is correct
12 Correct 563 ms 128608 KB Output is correct
13 Correct 1095 ms 131016 KB Output is correct
14 Correct 1694 ms 142304 KB Output is correct
15 Incorrect 649 ms 138336 KB Output isn't correct
16 Halted 0 ms 0 KB -