//Self-control leads to consistency.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll int
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define EPS 0.000001
struct greateri
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
typedef tree<
pair<int,dos>,
null_type,
less<pair<int,dos>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<
dos,
null_type,
less<dos>,
rb_tree_tag,
tree_order_statistics_node_update>
kalo;
kalo X1;
ordered_set X;
int p[100001];
int seg[1000001];
int zap[1000001];
int sparse[1000001][101];
set<pair<dos,int>>ko,zo;
void update(int p,int l,int r,int index,int val){
if(l==r && l==index){
seg[p]=val;
return;
}
ll med=(l+r)>>1;
if(index<=med)
update(p*2,l,med,index,val);
else update(p*2+1,med+1,r,index,val);
seg[p]=max(seg[p*2],seg[p*2+1]);
}
int query(int p,int l,int r,int l1,int r1){
if(l>=l1 && r<=r1){
return seg[p];
}
if(l>r || l>r1 || l1>r)return -INF;
ll med=(l+r)>>1;
return max(query(p*2,l,med,l1,r1),query(p*2+1,med+1,r,l1,r1));
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
flash;
vedos prep;
for (int i = 0; i < N; ++i)
{
X1.insert({i,i});
}
for (int i = 0; i < C; ++i)
{
ll l=S[i],r=E[i];
ll yo,zo;
auto n=X1.find_by_order(l);
yo=(*n).first;
auto m=X1.find_by_order(r);
zo=(*m).second;
for (int j = r; j >= l; --j)
{
auto u=X1.find_by_order(j);
X1.erase(u);
}
X1.insert({yo,zo});
prep.pb({yo,zo});
}
int ini=0;
for(auto it:prep){
ko.insert({{it.first,it.second},ini});
zo.insert({{it.second,it.first},ini});
ini++;
}
for (int i = 0; i < N-1; ++i)
{
update(1,0,N*2-1,i*2,K[i]);
update(1,0,N*2-1,i*2+1,-INF);
}
ll yoz=log2(N*2)+1;
zap[1] = 0;
for (int i = 2; i <= N*2; i++)
{
zap[i] = zap[i/2] + 1;
}
for (int i = 0; i < N-1; i++)
{
sparse[i*2][0]=K[i];
sparse[i*2+1][0]=-INF;
}
for (int j = 1; j <= yoz; j++)
for (int i = 0; i + (1 << j) <= N*2; i++)
{
sparse[i][j] = max(sparse[i][j-1], sparse[i + (1 << (j - 1))][j - 1]);
//debugs(i,j)
//debug(sparse[i][j])
}
int j = zap[7 - 0 + 1];
int minimum = max(sparse[0][j], sparse[7 - (1 << j) + 1][j]);
//debugs(minimum,j)
ve cur;
dos best={-INF,0};
int index=0;
for(auto it:prep){
if(0>=it.first && 0<=it.second){
cur.pb(index);
auto f=ko.lower_bound({{it.first,it.second},-INF});
X.insert({(*f).second,(*f).first});
}
index++;
}
int l=0,r=sz(cur)-1;
ll ans=-1;
while(l<=r){
ll med=(l+r)>>1;
auto u=prep[cur[med]];
auto zel=0;
if(u.first==0){
zel=max(query(1,0,N*2-1,u.first*2,(u.second)*2-1),R);
}
if(zel==R){
ans=med+1;
l=med+1;
}
else r=med-1;
}
if(ans==-1)ans=0;
if(best.first<ans)
best=max(best,{ans,0});
for (int i = 1; i < N; ++i)
{
//debug(i)
auto v=ko.lower_bound({{i,-INF},-INF});
while(v!=ko.end() && (*v).first.first==i){
X.insert({(*v).second,(*v).first});
v++;
}
l=0,r=sz(X)-1;
ans=-1;
while(l<=r){
ll med=(l+r)>>1;
auto lo=X.find_by_order(med);
auto u=(*lo).second;
auto zel=0;
if(i>u.first && i<=u.second){
int L=u.first*2,RO=(u.second)*2-1;
int j = zap[RO - L + 1];
int minimum = max(sparse[L][j], sparse[RO - (1 << j) + 1][j]);
//debugs(L,RO)
//debugs(minimum,R)
zel=max(minimum,R);
}
else if(i==u.first){
int L=(u.first-1)*2+1,RO=(u.second)*2-1;
int j = zap[RO - L + 1];
int minimum = max(sparse[L][j], sparse[RO - (1 << j) + 1][j]);
zel=max(minimum,R);
}
if(zel==R){
ans=med+1;
l=med+1;
}
else r=med-1;
}
if(ans==-1)ans=0;
if(best.first<ans)
best=max(best,{ans,i});
auto l=zo.lower_bound({{i,-INF},-INF});
while(l!=zo.end() && (*l).first.first==i){
X.erase({(*l).second,{(*l).first.second,(*l).first.first}});
l++;
}
}
return best.second;
}
Compilation message
tournament.cpp:8: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
8 | #pragma GCC optimization ("O3")
|
tournament.cpp:9: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
9 | #pragma GCC optimization ("unroll-loops")
|
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:127:7: warning: unused variable 'minimum' [-Wunused-variable]
127 | int minimum = max(sparse[0][j], sparse[7 - (1 << j) + 1][j]);
| ^~~~~~~
tournament.cpp: In function 'void setIO(std::string)':
tournament.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
31 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tournament.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
32 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
896 KB |
Output is correct |
| 4 |
Correct |
2 ms |
896 KB |
Output is correct |
| 5 |
Correct |
1 ms |
768 KB |
Output is correct |
| 6 |
Correct |
2 ms |
896 KB |
Output is correct |
| 7 |
Correct |
2 ms |
896 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 9 |
Correct |
1 ms |
768 KB |
Output is correct |
| 10 |
Correct |
1 ms |
768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
17 ms |
5504 KB |
Output is correct |
| 3 |
Correct |
10 ms |
4864 KB |
Output is correct |
| 4 |
Correct |
17 ms |
5376 KB |
Output is correct |
| 5 |
Correct |
16 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
13 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
18 ms |
5504 KB |
Output is correct |
| 8 |
Correct |
16 ms |
5376 KB |
Output is correct |
| 9 |
Correct |
7 ms |
4864 KB |
Output is correct |
| 10 |
Correct |
17 ms |
5248 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
179 ms |
46580 KB |
Output is correct |
| 2 |
Correct |
579 ms |
103016 KB |
Output is correct |
| 3 |
Correct |
220 ms |
89720 KB |
Output is correct |
| 4 |
Correct |
520 ms |
99812 KB |
Output is correct |
| 5 |
Correct |
529 ms |
97652 KB |
Output is correct |
| 6 |
Correct |
371 ms |
92400 KB |
Output is correct |
| 7 |
Correct |
538 ms |
100840 KB |
Output is correct |
| 8 |
Correct |
560 ms |
101052 KB |
Output is correct |
| 9 |
Correct |
215 ms |
89464 KB |
Output is correct |
| 10 |
Correct |
220 ms |
89592 KB |
Output is correct |
