제출 #540296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540296		new_acc	Aliens (IOI16_aliens)	C++14	0 / 100	2093 ms	340 KiB

aliens

    #include<bits/stdc++.h>
    #define fi first
    #define se second
    #define pitem item*
    using namespace std;
    typedef unsigned long long ll;
    typedef vector<int> vi;
    typedef vector<ll> vl;
    const ll M=1e6+10;
    const ll N=1e5+10;
    const ll SS=1<<20;
    const ll INFi=1e9;
    const ll INFl=1e12;
    struct f{
        ll a,b;
        ll ind;
        ll operator()(ll x){
            return a*x+b;
        }
    };
    struct item{
        f fun;
        item *l,*r;
    };
    pair<ll,ll> dp[N];
    f nullp;
    bool cmp(f a,f b,ll p,ll k){
        if(a.b==INFl) return 0;
        if(b.b==INFl) return 1;
        if((a(p)<b(p) and a(k)<b(k)) or (a(p)<=b(p) and a(k)<b(k)) or (a(p)<b(p) and a(k)<=b(k))) return 1;
        if(a(p)==b(p) and a(k)==b(k) and dp[a.ind].se<dp[b.ind].se) return 1;
        return 0;
    }
    pitem upd(pitem v,f x,ll p=0,ll k=SS-1){
        if(p>k) return nullptr;
        if(!v){
            v=new item;
            v->l=nullptr,v->r=nullptr,v->fun=x;
            return v;
        }
        ll sr=(p+k)>>1;
        if(cmp(x,v->fun,p,sr)){
            v->r=upd(v->r,v->fun,sr+1,k);
            v->fun=x;
        }else if(cmp(x,v->fun,sr+1,k)){
            v->l=upd(v->l,v->fun,p,sr);
            v->fun=x;
        }else if(cmp(v->fun,x,p,sr))
            v->r=upd(v->r,x,sr+1,k);
        else v->l=upd(v->l,x,p,sr);
        return v;
    }
    f Query(pitem v,ll x,ll p=0,ll k=SS-1){
        if(!v) return nullp;
        f pom;
        if(x<=((p+k)>>1)) pom=Query(v->l,x,p,(p+k)>>1);
        else pom=Query(v->r,x,((p+k)>>1)+1,k);
        if(cmp(v->fun,pom,x,x)) return v->fun;
        return pom;
    }
    void clear(pitem v){
        if(!v) return;
        clear(v->l),clear(v->r);
        delete(v);
    }
    ll t[N],l,val[N],mini[M],mini2[M],kw[N];
    ll res=INFl;
    ll wsp(ll i){
        if(t[i]-val[i]+1>kw[i]) return INFi;
        if(val[i]>t[i]) return 0;
        return (ll)(t[i]-val[i]+1)*(ll)(t[i]-val[i]+1);
    }
    f func(ll i){
        ll w=wsp(i);
        if(w==INFi) return nullp;
        f pom;
        pom.a=-2LL*val[i],pom.b=dp[i].fi+(ll)val[i]*(ll)val[i]+1LL-2LL*(ll)val[i]-(ll)w;
        pom.ind=i;
        return pom;
    }
    bool check(ll c,ll k){
        pitem v=nullptr;
        ll mm=INFi;
        for(ll i=1;i<=l;i++){
            mm=min(mm,mini[t[i]]);
            ll pom1=INFl;
            f curr=Query(v,t[i]);
            if(curr.b!=INFl) pom1=curr((ll)t[i])+(ll)t[i]*(ll)t[i]+2LL*(ll)t[i]+c;
            dp[i]={(ll)(t[i]-mm+1)*(ll)(t[i]-mm+1)+c,1};    
            kw[i]=t[i]-mm+1;
            if(dp[i].fi>pom1){
                dp[i]={pom1,dp[curr.ind].se+1};
                kw[i]=t[i]-val[curr.ind]+1;
            }
            if(i!=l){
                f pom2=func(i);
                if(pom2.b!=INFl) v=upd(v,pom2);
            }
        }
        clear(v);
        if(dp[l].se<=k){
            res=dp[l].fi-(ll)k*c;
            return 1;
        }
        return 0;
    }
    ll take_photos(int n,int m,int k,vi r,vi c){
        nullp.a=INFi,nullp.b=INFl;
        for(ll i=1;i<=m;i++) mini[i]=INFi;
        for(ll i=1;i<=n;i++){
            r[i-1]++,c[i-1]++;
            if(r[i-1]>c[i-1]) swap(r[i-1],c[i-1]);
            mini[c[i-1]]=min(mini[c[i-1]],(ll)r[i-1]);
        }
        ll akt=INFi;
        for(ll i=m;i>=1;i--){
            mini2[i]=akt;
            akt=min(akt,mini[i]);
        }
        for(ll i=1;i<=m;i++) if(mini[i]!=INFi) t[++l]=i,val[l]=mini2[i];
        ll pocz=0,kon=1000LL*1000LL*1000LL*1000LL+10LL;
        while(pocz<=kon){
            ll sr=(pocz+kon)>>1;
            if(check(sr,k)) kon=sr-1;
            else pocz=sr+1;
        }
        return res;
    }
    /*ll main(){
        ll n,m,k;
        cin>>n>>m>>k;
        vi r,c;
        for(ll i=1,a,b;i<=n;i++){
            cin>>a>>b;
            r.push_back(a),c.push_back(b);
        }
        cout<<take_photos(n,m,k,r,c)<<"\n";
    }*/

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'll take_photos(int, int, int, vi, vi)':
aliens.cpp:109:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
  109 |         for(ll i=1;i<=m;i++) mini[i]=INFi;
      |                    ~^~~
aliens.cpp:110:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
  110 |         for(ll i=1;i<=n;i++){
      |                    ~^~~
aliens.cpp:120:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
  120 |         for(ll i=1;i<=m;i++) if(mini[i]!=INFi) t[++l]=i,val[l]=mini2[i];
      |                    ~^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40