## Submission #202238

# Submission time Handle Problem Language Result Execution time Memory
202238 2020-02-14T11:41:18 Z anonymous Teams (IOI15_teams) C++14
0 / 100
1473 ms 147424 KB
```#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;
}
}
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;
}
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) {
}
}

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();
^```

#### Subtask #1 0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #2 0 / 13.0

# Verdict Execution time Memory 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 -

#### Subtask #3 0 / 43.0

# Verdict Execution time Memory 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 -

#### Subtask #4 0 / 23.0

# Verdict Execution time Memory 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 -