Submission #1027366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027366		boyliguanhan	Aliens (IOI16_aliens)	C++17	100 / 100	662 ms	48720 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define sq(k) (k)*(k)
typedef long long ll;
using namespace std;
ll VL[100100],rev[100100];
pair<ll,int>dp[100100];
struct seg{
    ll k,b,cnt;
    inline pair<ll,int> operator()(int x){
        return {k*x+b,cnt};    
    }
    seg(){k=0,b=1e18,cnt=0;}
    seg(ll k_,ll b_,ll cnt_){k=k_,b=b_,cnt=cnt_;}
};
struct link_cut_tree{
    seg T[1<<20];
    int lc[1<<20];
    int rc[1<<20];
    int CC;
    int rt;
    void upd(int &i,int l,int r,seg SG){
        if(!i)return void(T[i=++CC]=SG);
        if(l==r-1) {
            if(T[i](l)>SG(l))
                swap(T[i],SG);
            return;
        }
        if(T[i].k>SG.k)swap(T[i],SG);
        if(T[i](l+r>>1)<SG(l+r>>1))
            return upd(lc[i],l,l+r>>1,SG);
        swap(T[i],SG),upd(rc[i],l+r>>1,r,SG);
    }
    pair<ll,int> qry(int i,int l,int r,int p){
        if(!i) return {(ll)1e18,0};
        if(l==r-1)return T[i](p);
        if(l+r>>1<=p)
            return min(T[i](p),qry(rc[i],l+r>>1,r,p));
        return min(T[i](p),qry(lc[i],l,l+r>>1,p));
    }
    void reset(){
        rt=0;
        for(int i=1;i<=CC;i++)
            lc[i]=rc[i]=0;
        CC=0;
    }
    inline void addline(ll cnt,ll k,ll b){
        upd(rt,1,1e6+1,seg(k,b,cnt));
    }
    inline pair<ll,int>querypos(int pos){
        return qry(rt,1,1e6+1,pos);
    }
    link_cut_tree(){rt=CC=0;memset(lc,0,sizeof lc);memset(rc,0,sizeof rc);}
} LCT;
ll whttoad(int i){
    if(rev[i]>=VL[i+1])
        return sq(rev[i]-VL[i+1]+1);
    return 0;
}
int dodp(ll pen,int n){
    LCT.reset();
    LCT.addline(0,-2*VL[1]+2,sq(VL[1]-1));
    for(int i=1;i<=n;i++) {
        dp[i]=LCT.querypos(rev[i]);
        dp[i].second++;
        dp[i].first+=pen+sq(rev[i]);
        LCT.addline(dp[i].second,-2*VL[i+1]+2,sq(VL[i+1]-1)+dp[i].first-whttoad(i));
    }
    return dp[n].second;
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    ll MXX=m;
    swap(m,n);
    map<int,int>mp;
    int CC=0;
    map<int,int>mp2;
    for(int i=0;i<m;i++){
        r[i]++;c[i]++;
        if(r[i]>c[i]) swap(r[i],c[i]);
        mp[c[i]];
        if(mp2.count(c[i]))
            mp2[c[i]]=min(mp2[c[i]],r[i]);
        else mp2[c[i]]=r[i];
    }
    vector<int>todie;
    int sfc=1e9;
    auto it=mp2.end();
    do {
        it--;
        if(it->second>=sfc)
            todie.push_back(it->first);
        else sfc=it->second;
    }while(it!=mp2.begin());
    for(auto i:todie)
        mp.erase(i),mp2.erase(i);
    for(auto&[i,j]:mp)
        rev[j=++CC]=i,VL[j]=mp2[i];
    n=mp.size();
    ll L=0,R=MXX*MXX,res=0;
    while(L<=R){
        ll mid=L+R>>1;
        if(dodp(mid,n)<=k)
            R=mid-1,res=mid;
        else L=mid+1;
    }
    dodp(res,n);
    return dp[n].first-res*k;
}

Compilation message (stderr)

aliens.cpp: In member function 'void link_cut_tree::upd(int&, int, int, seg)':
aliens.cpp:31:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         if(T[i](l+r>>1)<SG(l+r>>1))
      |                 ~^~
aliens.cpp:31:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         if(T[i](l+r>>1)<SG(l+r>>1))
      |                            ~^~
aliens.cpp:32:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |             return upd(lc[i],l,l+r>>1,SG);
      |                                ~^~
aliens.cpp:33:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         swap(T[i],SG),upd(rc[i],l+r>>1,r,SG);
      |                                 ~^~
aliens.cpp: In member function 'std::pair<long long int, int> link_cut_tree::qry(int, int, int, int)':
aliens.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         if(l+r>>1<=p)
      |            ~^~
aliens.cpp:39:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |             return min(T[i](p),qry(rc[i],l+r>>1,r,p));
      |                                          ~^~
aliens.cpp:40:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         return min(T[i](p),qry(lc[i],l,l+r>>1,p));
      |                                        ~^~
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:102:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         ll mid=L+R>>1;
      |                ~^~

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