Submission #671101

#	Time	Username	Problem	Language	Result	Execution time	Memory
671101		victor_gao	Teams (IOI15_teams)	C++17	100 / 100	1237 ms	345716 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
#define pii pair<int,int>
#define x first
#define y second
#define MAXN 500005
using namespace std;
int L[MAXN],R[MAXN],n,root[MAXN];
struct Node{
    int l,r,lch,rch,val;
    Node(int _l=0,int _r=0,int a=0,int b=0,int c=0):l(_l),r(_r),lch(a),rch(b),val(c){}
};
struct segtree{
    vector<Node>seg;
    int num=0;
    int add_node(int l,int r){
        seg.push_back(Node(l,r,0,0,0));
        return num++;
    }
    void build(int i){
        int l=seg[i].l,r=seg[i].r,mid=(l+r)>>1;
        if (l==r) return;
        seg[i].lch=add_node(l,mid);
        seg[i].rch=add_node(mid+1,r);
        build(seg[i].lch); build(seg[i].rch);
    }
    void Insert(int i,int j,int p,int c){
        int l=seg[i].l,r=seg[i].r,mid=(l+r)>>1;
        if (l==r){
            seg[i].val+=c;
            return;
        }
        if (p<=mid){
            seg[i].lch=add_node(l,mid); seg[i].rch=seg[j].rch;
            seg[seg[i].lch]=seg[seg[j].lch];
            Insert(seg[i].lch,seg[j].lch,p,c);
            seg[i].val=seg[seg[i].lch].val+seg[seg[i].rch].val;
        } 
        else {
            seg[i].rch=add_node(mid+1,r); seg[i].lch=seg[j].lch;
            seg[seg[i].rch]=seg[seg[j].rch];
            Insert(seg[i].rch,seg[j].rch,p,c);
            seg[i].val=seg[seg[i].rch].val+seg[seg[i].lch].val;
        }
    }
    int query(int i,int j,int ll,int rr){
        // 計算 版本 i~j ll~rr 點的個數
        // 也就是 L1~L2 ll<=R<=rr 的點的個數
        int l=seg[i].l,r=seg[i].r,mid=(l+r)>>1;
        if (ll>rr) return 0;
        if (ll<=l&&rr>=r)
            return seg[i].val-seg[j].val;
        if (rr<=mid) return query(seg[i].lch,seg[j].lch,ll,rr);
        else if (ll>mid) return query(seg[i].rch,seg[j].rch,ll,rr);
        else return query(seg[i].lch,seg[j].lch,ll,mid)+query(seg[i].rch,seg[j].rch,mid+1,rr);
    }
    int query_pos(int i,int j,int need){
        int l=seg[i].l,r=seg[i].r;
        if (l==r) return l;
        int tmp=seg[seg[i].lch].val-seg[seg[j].lch].val;
        if (tmp<need) return query_pos(seg[i].rch,seg[j].rch,need-tmp);
        else return query_pos(seg[i].lch,seg[j].lch,need);
    }
    void debug(int i){
        cout<<seg[i].l<<" "<<seg[i].r<<" -> "<<seg[i].val<<'\n';
        if (seg[i].l==seg[i].r)
            return;
        debug(seg[i].lch); debug(seg[i].rch);
    }
}seg;
void init(int N, int A[], int B[]) {
    n=N;
    vector<pii>all;
    for (int i=1;i<=n;i++){
        L[i]=A[i-1]; R[i]=B[i-1];
        all.push_back({L[i],R[i]});
    }
    sort(all.begin(),all.end());
    root[0]=seg.add_node(1,n+1);
    seg.build(0);
    for (int i=1,j=0;i<=n;i++){
        root[i]=root[i-1];
        while (j<n&&all[j].x==i){
            int nrt=seg.add_node(1,n+1);
            seg.Insert(nrt,root[i],all[j].y,1);
            root[i]=nrt; j++;
        }
    }
}
int H[MAXN],last[MAXN],K[MAXN];
int can(int M, int NK[]) {
    for (int i=0;i<=M+5;i++){
        last[i]=0; H[i]=0; K[i]=0;
    }
    H[0]=n+1;
    for (int i=1;i<=M;i++)
        K[i]=NK[i-1];
    sort(K+1,K+1+M);
    vector<int>st;
    for (int i=1;i<=M;i++){
        while (!st.empty()&&H[st.back()]<K[i]) st.pop_back();
        int need=K[i]; last[i]=0; H[i]=K[i]-1;
        if (K[i]>n) return 0;
        while (!st.empty()){
            int j=st.back();
            int h=H[j];
            if (K[i]==K[j]){
                H[i]=H[j]; last[i]=last[j];
                st.pop_back();
                continue;
            }
            int get=seg.query(root[K[i]],root[K[j]],H[i]+1,h)+last[j]+last[i];
            if (get<need){
                need-=get; H[i]=h; last[i]=0;
                st.pop_back();
            }
            else break;
        }
        int j=(st.empty()) ? 0 : st.back();
        int out=seg.query(root[K[i]],root[K[j]],1,H[i]);
        int l=seg.query_pos(root[K[i]],root[K[j]],out+need-last[i]);
        l=min(l,H[j]);
     //   cout<<j<<" -> "<<out<<" "<<need<<" "<<last[i]<<'\n';
        /*
        int l=H[i],r=H[j];
        while (l<r){
            int mid=(l+r)>>1;
            int val=seg.query(root[K[i]],root[K[j]],H[i]+1,mid)+last[i];
            if (val>=need) r=mid;
            else l=mid+1;
        }
        */
        int can_use=seg.query(root[K[i]],root[K[j]],H[i]+1,l)+last[i];
        H[i]=l;
        while (!st.empty()&&H[i]==H[st.back()]){
            can_use+=last[st.back()];
            st.pop_back();
        }
        last[i]=can_use-need;
      //  cout<<i<<" "<<K[i]<<" : "<<H[i]<<' '<<last[i]<<'\n';
        if (can_use<need)
            return 0;
        st.push_back(i);
    }
    return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23