#include "teams.h"
#include<vector>
#include<map>
#include<algorithm>
#include<cassert>
#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 + PST.Sum(S.back().l, S.back().r, 0, S.back().h), S.back().l, S.back().r); //pos of first point kept
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;
}
}
}
}
return(true);
}
Compilation message
teams.cpp: In member function 'void PersistentSegtree::init()':
teams.cpp:61: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:86: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:86:9: warning: unused variable 'N' [-Wunused-variable]
int N=Students.size();
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
89 ms |
28396 KB |
Output is correct |
| 2 |
Correct |
88 ms |
28268 KB |
Output is correct |
| 3 |
Correct |
103 ms |
28392 KB |
Output is correct |
| 4 |
Incorrect |
115 ms |
28784 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
98 ms |
28780 KB |
Output is correct |
| 2 |
Correct |
90 ms |
28780 KB |
Output is correct |
| 3 |
Correct |
441 ms |
31724 KB |
Output is correct |
| 4 |
Incorrect |
114 ms |
28780 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
598 ms |
141408 KB |
Output is correct |
| 2 |
Correct |
585 ms |
141408 KB |
Output is correct |
| 3 |
Correct |
1473 ms |
147424 KB |
Output is correct |
| 4 |
Incorrect |
746 ms |
141408 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
