#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define o_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<bool> v;
vector<pair<int,int> >q;
vector<pair<int,int> >group;
vector<pair<int,int> >x[100010];
o_set sx,dx;
int GetBestPosition(int N,int C,int R,int *K,int *S,int *E){
for(int i=0;i<N-1;i++){
v.push_back(K[i]>R);
}
for(int i=0;i<N;i++){
sx.insert(i);
dx.insert(i);
}
for(int i=0;i<C;i++){
auto l=sx.find_by_order(S[i]);
auto r=dx.find_by_order(E[i]);
int a=*l,b=*r;
q.push_back({a,b});
l++;
vector<int> elim;
while(l!=sx.end() && *l<=b){
elim.push_back(*l);
l++;
}
for(int y:elim)sx.erase(y);
elim.clear();
r--;
while(*r>=a){
elim.push_back(*r);
if(r==dx.begin())break;
r--;
}
for(int y:elim)dx.erase(y);
}
for(int i=0;i<N-1;i++){
if(v[i]==0){
if(i==0 || v[i-1]==1)group.push_back({i,i});
else group.back().second++;
}
}
for(int i=0;i<C;i++){
int pos=upper_bound(group.begin(),group.end(),q[i])-group.begin();
if(pos==group.size() || q[i].first<group[pos].first)pos--;
if(pos<0)continue;
if(q[i].first>=group[pos].first && group[pos].second>=q[i].second-1)x[pos].push_back(q[i]);
}
int ma=0,best=0;
for(int i=0;i<group.size();i++){
if(x[i].size()<=ma)continue;
vector<int> k(group[i].second-group[i].first+100,0);
for(int j=0;j<x[i].size();j++){
k[x[i][j].first-group[i].first]++;
k[x[i][j].second-group[i].first+1]--;
}
for(int j=0;j<k.size();j++){
if(j>0)k[j]+=k[j-1];
if(k[j]>ma){
ma=k[j];
best=j+group[i].first;
}
}
}
//cout<<ma<<endl;
return best;
}
/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);
int main() {
int tmp;
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
assert(tmp == 0);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
assert(tmp == 0);
int N, C, R;
int *K, *S, *E;
tmp = scanf("%d %d %d", &N, &C, &R);
assert(tmp == 3);
K = (int*) malloc((N-1) * sizeof(int));
S = (int*) malloc(C * sizeof(int));
E = (int*) malloc(C * sizeof(int));
int i;
for (i = 0; i < N-1; i++) {
tmp = scanf("%d", &K[i]);
assert(tmp == 1);
}
for (i = 0; i < C; i++) {
tmp = scanf("%d %d", &S[i], &E[i]);
assert(tmp == 2);
}
printf("%d\n", GetBestPosition(N, C, R, K, S, E));
return 0;
}*/
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
*/
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:51:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(pos==group.size() || q[i].first<group[pos].first)pos--;
~~~^~~~~~~~~~~~~~
tournament.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<group.size();i++){
~^~~~~~~~~~~~~
tournament.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(x[i].size()<=ma)continue;
~~~~~~~~~~~^~~~
tournament.cpp:59:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<x[i].size();j++){
~^~~~~~~~~~~~
tournament.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<k.size();j++){
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2688 KB |
Output is correct |
3 |
Correct |
2 ms |
2688 KB |
Output is correct |
4 |
Correct |
3 ms |
2688 KB |
Output is correct |
5 |
Correct |
2 ms |
2688 KB |
Output is correct |
6 |
Correct |
2 ms |
2688 KB |
Output is correct |
7 |
Correct |
2 ms |
2688 KB |
Output is correct |
8 |
Correct |
3 ms |
2688 KB |
Output is correct |
9 |
Correct |
2 ms |
2688 KB |
Output is correct |
10 |
Correct |
2 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2816 KB |
Output is correct |
2 |
Correct |
9 ms |
3200 KB |
Output is correct |
3 |
Correct |
7 ms |
3200 KB |
Output is correct |
4 |
Correct |
9 ms |
3200 KB |
Output is correct |
5 |
Correct |
8 ms |
3200 KB |
Output is correct |
6 |
Correct |
10 ms |
3200 KB |
Output is correct |
7 |
Correct |
8 ms |
3200 KB |
Output is correct |
8 |
Correct |
9 ms |
3200 KB |
Output is correct |
9 |
Correct |
7 ms |
3200 KB |
Output is correct |
10 |
Correct |
11 ms |
3328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
8184 KB |
Output is correct |
2 |
Correct |
227 ms |
13304 KB |
Output is correct |
3 |
Correct |
188 ms |
13176 KB |
Output is correct |
4 |
Correct |
222 ms |
15096 KB |
Output is correct |
5 |
Correct |
214 ms |
14584 KB |
Output is correct |
6 |
Correct |
265 ms |
14836 KB |
Output is correct |
7 |
Correct |
223 ms |
15136 KB |
Output is correct |
8 |
Correct |
223 ms |
14968 KB |
Output is correct |
9 |
Correct |
166 ms |
13684 KB |
Output is correct |
10 |
Correct |
188 ms |
13176 KB |
Output is correct |