Submission #1036407

#TimeUsernameProblemLanguageResultExecution timeMemory
10364078pete8Jousting tournament (IOI12_tournament)C++17
0 / 100
1087 ms5816 KiB
#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=1e5+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 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],dp[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;
  v.clear();
  n=N,q=C;
  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(j);
    }
    node++;
    for(auto j:up)t.update(j,-1);
  }
  node--;
  solve(node);
  solve2(node);
  int ans=0;
  for(int i=0;i<n;i++)ans=max(ans,add[i]);
  //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:30: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   42 |   void update(int pos,int val){
      |                              ^
tournament.cpp:46:16: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 |   int get(int x){
      |                ^
tournament.cpp:58:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   58 | void solve(int cur){
      |                   ^
tournament.cpp:70:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   70 | void solve2(int cur){
      |                    ^
tournament.cpp: In function 'void solve2(int)':
tournament.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   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){
      |                                                                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...