Submission #945726

#	Time	Username	Problem	Language	Result	Execution time	Memory
945726		beepbeepsheep	Jousting tournament (IOI12_tournament)	C++17	100 / 100	284 ms	31176 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>

const ll inf=1e15;
const ll maxn=1e5+5;
const ll mod=1e9+7;
vector<ii> v;
stack<ii> s; //ending point, value

struct node2{
    ll s,e,m,val,flag;
    node2 *l,*r;
    node2 (ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,val=e-s+1,flag=0;
        if (s!=e) l=new node2(s,m),r=new node2(m+1,e);
    }
    void prop(){
        if (!flag) return;
        val=0;
        if (s==e){
            flag=0;
            return;
        }
        l->flag=flag;
        r->flag=flag;
        flag=0;
    }
    void upd(ll x, ll y){
        if (x<=s && e<=y){
            flag=1;
            return;
        }
        if (x>m) r->upd(x,y);
        else if (y<=m) l->upd(x,y);
        else l->upd(x,y),r->upd(x,y);
        l->prop(),r->prop();
        val=l->val+r->val;
    }
    ll query(ll x, ll y){
        prop();
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return l->query(x,y)+r->query(x,y);
    }
}*root2;
struct node{
    ll s,e,m;
    ll val;
    node *l,*r;
    node (ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,val=0;
        if (s!=e) l=new node(s,m),r=new node(m+1,e);
    }
    void upd(ll x, ll v){
        if (s==e){
            val=v;
            return;
        }
        if (x>m) r->upd(x,v);
        else l->upd(x,v);
        val=max(l->val,r->val);
    }
    ll query(ll x, ll y){
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return max(l->query(x,y),r->query(x,y));
    }
}*root;
ll n;
ll bsta(ll x, ll t){
    if (t==1){
        ll l=0,r=n,m;
        while (l!=r-1){
            m=(l+r)>>1;
            ll res=root2->query(1,m);
            if (res>=x) r=m;
            else l=m;
        }
        return r;
    } else{
        ll l=1,r=n+1,m;
        while (l!=r-1){
            m=(l+r)>>1;
            ll res=root2->query(1,m);
            if (res<=x) l=m;
            else r=m;
        }
        return l;
    }
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;
    root2=new node2(1,N);
    for (int i=0;i<C;i++){
        S[i]++,E[i]++;
        S[i]=bsta(S[i],1);
        E[i]=bsta(E[i],0);
        root2->upd(S[i]+1,E[i]);
        v.emplace_back(S[i],-E[i]);
        //cerr<<S[i]<<' '<<E[i]<<endl;
    }
    root=new node(1,N);
    for (int i=1;i<N;i++) root->upd(i,K[i-1]);
    ll ans=-1,pos=-1;
    sort(v.begin(),v.end());
    s.emplace(inf,0);
    for (auto [l,r]:v){
        r=-r;
        while (s.size() && l>s.top().first) s.pop();
        ll res=root->query(l,r-1);
        //cerr<<l<<' '<<r<<' '<<res<<endl;
        if (res>R){
            s.emplace(r,0);
        }
        else{
            ll endTime,val;
            tie(endTime,val)=s.top();
            s.emplace(r,val+1);
        }
        if (s.top().second>ans){
            ans=s.top().second;
            pos=l;
        }
    }
    return pos-1;

}

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