Submission #1137331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137331		t9unkubj	팀들 (IOI15_teams)	C++20	Compilation error	0 ms	0 KiB

teams

#define _GLIBCXX_DEBUG
#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){}
    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=new Node();
        nw->l=now->l;
        nw->r=now->r;
        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;
vc<np>root;
persistent_seg Seg(0);
void Init(int n_,vc<int>a,vc<int>b){
    n=n_;
    migi=vc<int>(n+2);
    root=vc<np>(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;
    }
    dbg(root);
}
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){
        dbg(i);
        auto f=[&](int idx)->int{
            int res=dp[idx];
            auto tar=root[k[i]];
            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);
}
namespace Brute{
    int n;
    vc<int>a,b;
    void init(int N,vc<int>A,vc<int>B){
        a=A;b=B;n=N;
    }
    int can(int m,vc<int>k){
        sort(all(k));
        multiset<int>que;
        vvc<int>in(n+2);
        vc<int>out(n+2);
        rep(i,n){
            in[a[i]].push_back(b[i]);
            out[b[i]]++;
        }
        vc<int>cnt(n+2);
        rep(i,m)cnt[k[i]]++;
        rep(i,n+2){
            for(auto&x:in[i])que.insert(x);
            rep(j,i*cnt[i]){
                if(!que.size())return 0;
                que.erase(que.begin());
            }
            rep(j,out[i])if(que.find(i)!=que.end())que.erase(que.find(i));
        }
        return 1;
    }
};
mt19937 mt;
void input(){
    int n;
    cin>>n;
    vc<int>a(n),b(n);
    rep(i,n)cin>>a[i]>>b[i];
    Init(n,a,b);
    int k;
    cin>>k;
    vc<int>m(k);
    rep(i,k)cin>>m[i];
    dbg(Can(k,m));
}
void run(){
    int n=3;
    vc<int>a(n),b(n);
    rep(i,n)a[i]=mt()%n+1,b[i]=mt()%n+1;
    rep(i,n)if(a[i]>b[i])swap(a[i],b[i]);
    Init(n,a,b);
    Brute::init(n,a,b);
    int q=1;
    while(q--){
        int m=2;
        vc<int>k(m);
        rep(i,m)k[i]=rand()%n+1;
        if(Can(m,k)!=Brute::can(m,k)){
            dbg(n,m,a,b,k);
            dbg(Can(m,k));
            dbg(Brute::can(m,k));
            assert(0);
        }
    }
}
int main(){input();}
/*
2 2
1 1
1 3
2 1 2

*/

Compilation message (stderr)

/usr/bin/ld: /tmp/cc1KWAvS.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccnhMUZ3.o:teams.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status