Submission #1027199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027199		vjudge1	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	4700 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#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(int k_,int b_,int cnt_){k=k_,b=b_,cnt=cnt_;}
};
struct link_cut_tree{
    seg T[100100];
    int lc[100100];
    int rc[100100];
    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(rc[i],l+r>>1,r,SG);
        swap(T[i],SG),upd(lc[i],l,l+r>>1,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+1>>r<=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;
    }
    void addline(int cnt,int k,int b){
        upd(rt,1,1e6+1,seg(k,b,cnt));
    }
    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){
        int mid=L+R>>1;
        if(dodp(mid,n)>k)
            L=mid+1;
        else R=mid-1,res=mid;
    }
    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:30:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         if(T[i](l+r>>1)<SG(l+r>>1))
      |                 ~^~
aliens.cpp:30:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         if(T[i](l+r>>1)<SG(l+r>>1))
      |                            ~^~
aliens.cpp:31:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |             return upd(rc[i],l+r>>1,r,SG);
      |                              ~^~
aliens.cpp:32:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         swap(T[i],SG),upd(lc[i],l,l+r>>1,SG);
      |                                   ~^~
aliens.cpp: In member function 'std::pair<long long int, int> link_cut_tree::qry(int, int, int, int)':
aliens.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         if(l+1>>r<=p)
      |            ~^~
aliens.cpp:38:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |             return min(T[i](p),qry(rc[i],l+r>>1,r,p));
      |                                          ~^~
aliens.cpp:39:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         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:101:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int mid=L+R>>1;
      |                 ~^~

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