Submission #1137321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137321		t9unkubj	Teams (IOI15_teams)	C++20	0 / 100	254 ms	89352 KiB

teams

#include "teams.h"
#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif


#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
struct persistent_seg{
    struct Node{
        Node*l;
        Node*r;
        int val;
        Node():l(nullptr),r(nullptr),val(0){}
    };
    int n;
    persistent_seg(int n):n(n){}
    void make(Node*now){
        if(now==nullptr)now=new Node();
    }
    Node* internal_set(int l,int r,int i,int x,Node*now){
        if(l+1==r){
            Node* res=new Node();
            res->val=x;
            return res;
        }
        int mid=l+r>>1;
        if(now->l==nullptr)now->l=new Node();
        if(now->r==nullptr)now->r=new Node();
        
        Node* nw=now;
        if(l<=i&&i<mid)nw->l=internal_set(l,mid,i,x,now->l);
        else nw->r=internal_set(mid,r,i,x,now->r);
        nw->val=(nw->l)->val+(nw->r)->val;
        return nw;
    }
    Node* set(int i,int x,Node*root){
        return internal_set(0,n,i,x,root);
    }
    int internal_prod(int nl,int nr,int l,int r,Node*now){
        if(l<=nl&&nr<=r)return now->val;
        if(nr<=l||r<=nl)return 0;
        int mid=nl+nr>>1;

        if(now->l==nullptr)now->l=new Node();
        if(now->r==nullptr)now->r=new Node();
        
        return internal_prod(nl,mid,l,r,now->l)+internal_prod(mid,nr,l,r,now->r);
    }
    int prod(int l,int r,Node*root){
        return internal_prod(0,n,l,r,root);
    }
};
struct segtree{
    int n;
    vc<int>node;
    segtree(int n):n(n),node(n*2){}
    void set(int i,int x){
        node[i+=n]=x;
        while(i>>=1)node[i]=node[i*2]+node[i*2+1];
    }
    int prod(int l,int r){
        l+=n,r+=n;
        int res=0;
        while(l<r){
            if(l&1)res+=node[l++];
            if(r&1)res+=node[--r];
            l/=2,r/=2;
        }
        return res;
    }
};
int n;
using np=persistent_seg::Node*;
//Kより右にある点の個数
vc<int>migi;
np root[(int)2e5+100];
persistent_seg Seg(0);
void Init(int n,vc<int>a,vc<int>b){
    migi.resize(n+2);
    Seg=persistent_seg(n+2);
    rep(i,n){
        migi[a[i]]++;
    }  
    rep(i,n+1)migi[i+1]+=migi[i];
    dbg(migi);
    np now=new persistent_seg::Node();
    vvc<int>ev(n+2);
    rep(i,n){
        ev[b[i]].push_back(a[i]);
    }
    drep(i,n+2){
        for(auto&x:ev[i]){
            now=Seg.set(x,Seg.prod(x,x+1,now)+1,now);
        }
        root[i]=now;
    }
}
void init(int N, int A[], int B[]) {
    n=N;
    vc<int>a(n);
    vc<int>b(n);
    rep(i,n)a[i]=A[i];
    rep(i,n)b[i]=B[i];
    Init(n,a,b);
}
int Can(int m,vc<int>k){
    sort(all(k));
    k.insert(k.begin(),0);
    vc<int>dp(m+1,1e9);
    dp[0]=0;
    int idx=0;
    REP(i,1,m+1){
        auto f=[&](int idx)->int{
            int res=dp[idx];
            auto tar=root[k[idx]];
            res+=Seg.prod(k[idx]+1,n+2,tar);
            res-=migi.back()-migi[k[i]];
            return res;
        };
        while(idx+1<i&&f(idx)>f(idx+1)){
            idx++;
        }
        chmin(dp[i],f(idx)-k[i]);
    }
    return *min_element(all(dp))>=0;
}
int can(int M, int K[]) {
    vc<int>k(M);
    rep(i,M)k[i]=K[i];
    return Can(M,k);
}
void run(){
    int n;
    cin>>n;
    int a[n],b[n];
    rep(i,n)cin>>a[i]>>b[i];
    init(n,a,b);
    int q;
    cin>>q;
    while(q--){
        int m;
        cin>>m;
        int k[m];
        rep(i,m)cin>>k[i];
        dbg(can(m,k));
    }
}
//int main(){run();}
/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1

*/

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