oj.uz

답안 #202233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202233 2020-02-14T10:47:51 Z anonymous 팀들 (IOI15_teams) C++14
13 / 100
 1687 ms 149984 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.push_back(New);}
        else {S.back().h=max(S.back().h, K[i]-1);}
        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();
         ^

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 248 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 6 ms 376 KB Output is correct
9 Correct 5 ms 380 KB Output is correct
10 Correct 5 ms 380 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 7 ms 376 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 464 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Incorrect 5 ms 376 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 28396 KB Output is correct
2 Correct 82 ms 28396 KB Output is correct
3 Correct 87 ms 28396 KB Output is correct
4 Correct 83 ms 29036 KB Output is correct
5 Correct 45 ms 25836 KB Output is correct
6 Correct 45 ms 25836 KB Output is correct
7 Correct 45 ms 25836 KB Output is correct
8 Correct 46 ms 26608 KB Output is correct
9 Correct 57 ms 26860 KB Output is correct
10 Correct 48 ms 26476 KB Output is correct
11 Correct 39 ms 26476 KB Output is correct
12 Correct 40 ms 26604 KB Output is correct
13 Correct 51 ms 27116 KB Output is correct
14 Correct 55 ms 27884 KB Output is correct
15 Correct 75 ms 29164 KB Output is correct
16 Correct 73 ms 29164 KB Output is correct
17 Correct 45 ms 26988 KB Output is correct
18 Correct 44 ms 26988 KB Output is correct

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 28780 KB Output is correct
2 Correct 91 ms 28908 KB Output is correct
3 Correct 377 ms 31724 KB Output is correct
4 Correct 83 ms 28780 KB Output is correct
5 Correct 177 ms 26096 KB Output is correct
6 Correct 152 ms 26092 KB Output is correct
7 Correct 53 ms 26220 KB Output is correct
8 Correct 131 ms 27316 KB Output is correct
9 Correct 54 ms 26732 KB Output is correct
10 Correct 105 ms 26832 KB Output is correct
11 Correct 112 ms 26988 KB Output is correct
12 Correct 190 ms 27244 KB Output is correct
13 Correct 330 ms 28144 KB Output is correct
14 Correct 465 ms 31852 KB Output is correct
15 Incorrect 169 ms 30060 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 141408 KB Output is correct
2 Correct 558 ms 141664 KB Output is correct
3 Correct 1395 ms 147296 KB Output is correct
4 Correct 538 ms 141536 KB Output is correct
5 Correct 500 ms 128100 KB Output is correct
6 Correct 447 ms 128096 KB Output is correct
7 Correct 228 ms 128096 KB Output is correct
8 Correct 419 ms 132836 KB Output is correct
9 Correct 299 ms 132960 KB Output is correct
10 Correct 297 ms 131296 KB Output is correct
11 Correct 364 ms 132064 KB Output is correct
12 Correct 552 ms 132960 KB Output is correct
13 Correct 1134 ms 136968 KB Output is correct
14 Correct 1687 ms 149984 KB Output is correct
15 Incorrect 678 ms 145408 KB Output isn't correct
16 Halted 0 ms 0 KB -