#include<iostream>
#include<map>
#include<utility>
#include<algorithm>
#include<vector>
#define MAXN 100005
using namespace std;
class PersistentSegtree {
int ST[MAXN * 30][3], R[MAXN], X[MAXN]={-1<<30}, V=1, P=1;
int put(int ind, int l, int r, int cur) {
if (l > ind || ind > r) {return(cur);}
if (l == r) {
ST[V][0] = ST[cur][0] + 1, V++;
return(V-1);
} else {
int mid = (l+r) >> 1, p = V;
V++;
ST[p][1] = put(ind, l, mid, ST[cur][1]);
ST[p][2] = put(ind, mid+1, r, ST[cur][2]);
ST[p][0] = ST[ST[p][1]][0] + ST[ST[p][2]][0];
return(p);
}
}
int ask(int lo, int hi, int l, int r, int cur) {
if (hi < l || lo > r || cur == 0) {return(0);}
if (lo <= l && hi >= r) {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]));
}
}
public:
void add(int x, int y) {
R[P] = put(y, 0, MAXN, R[P-1]);
X[P] = x, P++;
}
int Find(int x) { //largest index of largest not greater
int lo = 0, hi = P;
while (lo + 1 != hi) {
int mid = (lo + hi) >> 1;
if (X[mid] > x) {hi = mid;}
else {lo = mid;}
}
return(lo);
}
int sum(int xlo, int ylo, int xhi, int yhi) {
int q1 = Find(xlo - 1), q2 = Find(xhi);
return(ask(ylo, yhi, 0, MAXN, R[q2]) - ask(ylo, yhi, 0, MAXN, R[q1]));
}
} PST;
class UFsegtree {
int ST[MAXN*4];
public:
void build(int l, int r, int cur) {
if (l == r) {ST[cur]=1;}
else {
int mid = (l + r) >> 1;
build(l, mid, 2*cur);
build(mid+1, r, 2*cur+1);
ST[cur] = r - l + 1;
}
}
void upd(int ind, int l, int r, int cur) {
if (ind < l || ind > r) {return;}
if (l == r) {ST[cur]=0;}
else {
int mid = (l + r) >> 1;
upd(ind, l, mid, 2*cur);
upd(ind, mid+1, r, 2*cur+1);
ST[cur] = ST[2*cur] + ST[2*cur + 1];
}
}
int kth(int k, int l, int r, int cur) { //zero indexed
if (l == r) {return(l);}
int mid = (l + r) >> 1;
if (k >= ST[2*cur]) {return(kth(k - ST[2*cur], mid+1, r, 2*cur+1));}
else {return(kth(k, l, mid, 2*cur));}
}
} ST;
int Range[MAXN][2], val[MAXN];
int pt1, pt2, best;
vector <pair<int,int> > Seg;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
ST.build(0, N-1, 1);
for (int i=0; i<N; i++) {
Range[i][0]=Range[i][1]=i;
}
for (int i=0; i<C; i++) {
int li = ST.kth(S[i], 0, N-1, 1), ri = ST.kth(E[i], 0, N-1, 1);
Seg.push_back({Range[li][0], Range[ri][1]});
Range[li][1]=Range[ri][1];
for (int j=S[i]+1; j<=E[i]; j++) {
ST.upd(ST.kth(S[i]+1, 0, N-1, 1), 0, N-1,1);
}
}
sort(Seg.begin(), Seg.end());
for (auto s: Seg) {
PST.add(s.first, s.second);
}
K[N-1] = R;
pt2 = N-1; //rightmost good
pt1 = N-1; //leftmost good
for (int i=N-1; i>=0; i--) {
while (pt1 && K[pt1-1] < R) {pt1--;}
while (pt2 && K[pt2] > R) {pt2--;}
best = max(best, PST.sum(pt1, 0, MAXN, pt2));
if (!i) {break;}
swap(K[i], K[i-1]);
pt1=min(pt1, i-1);
}
return(best);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
9716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
