Submission #1036451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036451		8pete8	Jousting tournament (IOI12_tournament)	C++17	100 / 100	68 ms	35144 KiB

tournament

#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);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
  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;
  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:83:64: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   83 | int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
      |                                                                ^

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51