//#include "tournament.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second
struct sgt {
struct node {
int x=0, cant=0, lazy=0;
};
vector<node> t; int sz=1;
void push(int v) {
if (t[v].cant) {
t[2*v+1].cant=1;
t[2*v+2].cant=1;
}
if (!t[2*v+1].cant) t[2*v+1].lazy+=t[v].lazy;
if (!t[2*v+2].cant) t[2*v+2].lazy+=t[v].lazy;
t[v].x+=t[v].lazy;
t[v].lazy=0;
}
sgt(int n) {
while (sz<n) sz<<=1;
t.assign(4*sz,node());
}
void add(int v, int l, int r, int lx, int rx) {
//if (t[v].cant) return;
if (t[v].lazy) push(v);
if (rx<=l || r<=lx) return;
if (lx<=l && r<=rx) {
if (t[v].cant) return;
t[v].lazy++;
push(v);
return;
}
int m=(l+r)>>1;
add(2*v+1,l,m,lx,rx);
add(2*v+2,m,r,lx,rx);
}
void add(int l, int r) {
add(0,0,sz,l,r);
}
void set(int v, int l, int r, int lx, int rx) {
//if (t[v].cant) return;
if (t[v].lazy) push(v);
if (rx<=l || r<=lx) return;
if (lx<=l && r<=rx) {
t[v].cant=1; return;
}
int m=(l+r)>>1;
set(2*v+1,l,m,lx,rx);
set(2*v+2,m,r,lx,rx);
}
void set(int l, int r) {
set(0,0,sz,l,r);
}
void dfs(int v, int l, int r) {
if (t[v].lazy) push(v);
if (r-l==1) return;
int m=(l+r)>>1;
dfs(2*v+1,l,m);
dfs(2*v+2,m,r);
}
void dfs() {
dfs(0,0,sz);
}
};
struct RMQ {
vector<int> t; int sz=1;
void build(int v, int l, int r) {
if (r-l==1) return;
int m=(l+r)>>1;
build(2*v+1,l,m);
build(2*v+2,m,r);
t[v]=max(t[2*v+1],t[2*v+2]);
}
RMQ(vector<int>&a) {
int n=a.size();
while (sz<n) sz<<=1;
t.assign(2*sz,0);
forn(i,n) t[sz-1+i]=a[i];
build(0,0,sz);
}
int query(int v, int l, int r, int lx, int rx) {
if (rx<=l || r<=lx) return 0;
if (lx<=l && r<=rx) return t[v];
int m=(l+r)>>1;
int lq=query(2*v+1,l,m,lx,rx);
int rq=query(2*v+2,m,r,lx,rx);
return max(lq,rq);
}
int query(int l, int r) {
return query(0,0,sz,l,r);
}
};
const int sz=1<<20;
struct st {
st *L, *R;
int s;
st() {
L=R=NULL; s=0;
}
void add(int l, int r, int x) {
++s;
if (r-l==1) return;
int m=(l+r)>>1;
if (x<m) {
if (!L) L=new st();
L->add(l,m,x);
} else {
if (!R) R=new st();
R->add(m,r,x);
}
}
void add(int x) {
add(0,sz,x);
}
void del(int l, int r, int x) {
--s;
if (r-l==1) return;
int m=(l+r)>>1;
if (x<m) {
L->del(l,m,x);
} else {
R->del(m,r,x);
}
}
void del(int x) {
del(0,sz,x);
}
int kth(int l, int r, int k) {
if (r-l==1) return l;
int m=(l+r)>>1;
if (L) {
if (L->s>=k) return L->kth(l,m,k);
else return R->kth(m,r,k-L->s);
} else {
return R->kth(m,r,k);
}
}
int kth(int k) {
return kth(0,sz,k);
}
};
st segs;
int GetBestPosition(int n, int c, int z, int*k, int*s, int*e) {
vector<pi> q;
forn(i,n) segs.add(i); segs.add(1e6);
forn(i,c) {
int l=s[i], r=e[i];
int lq=segs.kth(l+1);
int rq=segs.kth(r+2)-1;
rq=min(rq,n-1);
q.pb({lq,rq});
for (int j=l+1; j<=r; ++j) {
int x=segs.kth(l+2);
segs.del(x);
}
}
vector<int> a(n-1); forn(i,n-1) a[i]=k[i];
sgt st(n);
RMQ rmq(a);
for(auto&x:q) {
int l=x.f, r=x.s;
int mx=rmq.query(l,r);
if (mx<z) st.add(l,r+1);
else st.set(l,r+1);
}
st.dfs();
int ans=0, best=0;
forn(i,n) {
if (st.t[st.sz-1+i].x>ans) {
ans=st.t[st.sz-1+i].x;
best=i;
}
}
return best;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:4:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
4 | #define forn(i,n) for(int i=0;i<n;++i)
| ^~~
tournament.cpp:157:3: note: in expansion of macro 'forn'
157 | forn(i,n) segs.add(i); segs.add(1e6);
| ^~~~
tournament.cpp:157:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
157 | forn(i,n) segs.add(i); segs.add(1e6);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
296 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
1 ms |
300 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1236 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1236 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1148 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1204 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
8608 KB |
Output is correct |
| 2 |
Correct |
107 ms |
17680 KB |
Output is correct |
| 3 |
Correct |
43 ms |
15308 KB |
Output is correct |
| 4 |
Correct |
105 ms |
17792 KB |
Output is correct |
| 5 |
Correct |
96 ms |
17296 KB |
Output is correct |
| 6 |
Correct |
96 ms |
16768 KB |
Output is correct |
| 7 |
Correct |
103 ms |
17628 KB |
Output is correct |
| 8 |
Correct |
101 ms |
17688 KB |
Output is correct |
| 9 |
Correct |
40 ms |
15192 KB |
Output is correct |
| 10 |
Correct |
44 ms |
15180 KB |
Output is correct |
