Submission #586938

#	Time	Username	Problem	Language	Result	Execution time	Memory
586938		krit3379	Jousting tournament (IOI12_tournament)	C++17	100 / 100	281 ms	13688 KiB

tournament

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using namespace __gnu_pbds;
using pii = pair<int,int>;
using piii = pair<int,pair<int,int>>;
#define N 100005

tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> s;
tree<piii,null_type,less<piii>,rb_tree_tag,tree_order_statistics_node_update> q;
pair<int,int> seg[N];
int dp[N],ma=-1,ans;
vector<int> op[N];

int val(int l,int r){
    if(l>r)return 0;
    if(l)return dp[r]-dp[l-1];
    return dp[r];
}

int ch(int l,int r,int m){
    return val(l,m-1)+val(m,r-1);
}

int GetBestPosition(int n,int c,int R,int *K,int *S,int *E) {
    int i,l,r,mid;
    for(i=0;i<n;i++)s.insert({i,i});
    for(i=0;i<c;i++){
        auto l=s.find_by_order(S[i]),r=s.find_by_order(E[i]);
        seg[i]={(*l).first,(*r).second};
        r++;
        while(l!=r)s.erase(l++);
        s.insert(seg[i]);
        op[seg[i].first].push_back(i+1);
        op[seg[i].second+1].push_back(-i-1);
    }
    for(i=0;i<n-1;i++){
        if(i)dp[i]+=dp[i-1];
        dp[i]+=K[i]>R;
    }
    for(i=0;i<n;i++){
        for(auto id:op[i]){
            if(id>0)q.insert({id-1,seg[id-1]});
            else q.erase({-id-1,seg[-id-1]});
        }
        l=0,r=((int)q.size())-1;
        while(l<=r){
            mid=(l+r)/2;
            auto it=q.find_by_order(mid);
            if(!ch((*it).second.first,(*it).second.second,i)){
                if(mid>ma)ma=mid,ans=i;
                l=mid+1;
            }
            else r=mid-1;
        }
    }
    return ans;
}

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