This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
//#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e9,minf=-1e9,lg=25;
int n,m,k,q;
vector<pii>v;
vector<int>adj[mxn+10];
int val[mxn+10],id[mxn+10],node;
struct fen{
int fwk[mxn+10];
void init(){for(int i=0;i<=n;i++)fwk[i]=0;}
void update(int pos,int val){
pos++;
for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;
}
int get(int x){
int pos=0,sum=0;
for(int i=lg;i>=0;i--){
if(pos+(1LL<<i)<=n&&fwk[pos+(1LL<<i)]+sum<x){
pos+=(1LL<<i);
sum+=fwk[pos];
}
}
return pos;
}
}t;
int dp[mxn+10],dp2[mxn+10];//normal dp,and shifted dp
void solve(int cur){
if(cur<n){
dp[cur]=val[cur];
if(cur)dp2[cur]=val[cur-1];
else dp2[cur]=k;
}
for(auto i:adj[cur]){
solve(i);
dp[cur]=max(dp[cur],dp[i]),dp2[cur]=max(dp2[cur],dp2[i]);
}
}
int add[mxn+10];
void solve2(int cur){
vector<int>pref,suf;
for(auto i:adj[cur])pref.pb(dp[i]),suf.pb(dp2[i]);
suf.pb(-1);
for(int i=adj[cur].size()-1;i>=0;i--)suf[i]=max(suf[i],suf[i+1]);
int l=-1;
for(int i=0;i<adj[cur].size();i++){
if(k>=max(l,suf[i+1]))add[adj[cur][i]]+=add[cur]+1;
l=max(l,pref[i]);
}
for(auto i:adj[cur])solve2(i);
}
bool repeat=0;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
//will this work??
//if(repeat)assert(0);
//repeat=1;
t.init();
v.clear();
n=N,q=C;
R=min(R,n);
k=R;
for(int i=0;i<C;i++,S++,E++)v.pb({*S,*E});
for(int i=0;i<n-1;i++,K++)val[i]=(*K);
val[n-1]=k;
for(int i=0;i<n;i++){
if(i)t.update(i,1);
id[i]=i;
}
node=n;
for(auto i:v){
vector<int>up;
for(int j=i.f;j<=i.s;j++){
int x=t.get(j);
adj[node].pb(id[x]);
id[x]=node;
if(j!=i.f)up.pb(x);
}
node++;
for(auto j:up)t.update(j,-1);
}
node--;
solve(node);
solve2(node);
int ans=0;
for(int i=0;i<n;i++)if(add[i]>add[ans])ans=i;
for(int i=0;i<=n;i++)adj[i].clear(),add[i]=0;
//cout<<ans<<"LL\n";
return ans;
}
Compilation message (stderr)
tournament.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
tournament.cpp:42:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
42 | void init(){for(int i=0;i<=n;i++)fwk[i]=0;}
| ^
tournament.cpp:43:30: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
43 | void update(int pos,int val){
| ^
tournament.cpp:47:16: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
47 | int get(int x){
| ^
tournament.cpp:59:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
59 | void solve(int cur){
| ^
tournament.cpp:71:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
71 | void solve2(int cur){
| ^
tournament.cpp: In function 'void solve2(int)':
tournament.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<adj[cur].size();i++){
| ~^~~~~~~~~~~~~~~~
tournament.cpp: At global scope:
tournament.cpp:84:64: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
84 | int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |