Submission #1018092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018092		khanhphucscratch	Aliens (IOI16_aliens)	C++14	100 / 100	253 ms	35704 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
#define int long long
using namespace std;
struct CHT
{
    vector<pair<int, int>> line;
    vector<int> info;
    vector<double> hull;
    double intersection(pair<int, int> x, pair<int, int> y)
    {
        return (double)(x.second - y.second) / (y.first - x.first);
    }
    void addline(pair<int, int> x, int inf)
    {
        while(hull.size() > 0 && intersection(x, line[line.size()-1]) <= hull[hull.size()-1]){
            hull.pop_back(); line.pop_back(); info.pop_back();
        }
        if(line.size() > 0) hull.push_back(intersection(line[line.size()-1], x));
        line.push_back(x);
        info.push_back(inf);
    }
    pair<int, int> bestval(int x)
    {
        if(line.size() == 0) return make_pair(1e15, 0);
        if(line.size() == 1) return make_pair(line[0].first*x+line[0].second, info[0]);
        int place = upper_bound(hull.begin(), hull.end(), x) - hull.begin();
        //cout<<line.size()<<" "<<info.size()<<" "<<place<<" "<<info[1]<<endl;
        if(place > 0 && line[place].first*x+line[place].second == line[place-1].first*x+line[place-1].second) return make_pair(line[place].first*x+line[place].second, min(info[place], info[place-1]));
        else return make_pair(line[place].first*x+line[place].second, info[place]);
    }
};
int dp[1000005], cnt[1000005], last[1000005];
inline bool cmp(pair<int, int> x, pair<int, int> y)
{
    return x.second < y.second || (x.second == y.second && x.first > y.first);
}
int take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c)
{
    //Transform to segments
    vector<pair<int, int>> segment;
    for(int i = 0; i < n; i++){
        if(r[i] <= c[i]) segment.push_back({r[i], c[i]+1});
        else segment.push_back({c[i], r[i]+1});
    }
    //Eliminate unnecessary segments
    sort(segment.begin(), segment.end(), cmp);
    vector<pair<int, int>> sus;
    for(pair<int, int> i : segment){
        while(sus.size() > 0 && sus[sus.size()-1].first >= i.first){
            sus.pop_back();
        }
        sus.push_back(i);
    }
    memset(last, -1, sizeof(last));
    for(pair<int, int> i : sus){
        last[i.second] = i.first;
        //cout<<i.first<<" "<<i.second<<endl;
    }
    //O(m log n log eps^-1) dp
    int le = 0, ri = 1e12, ans = 1e18, lamdaval;
    while(le <= ri){
        int lambd = (le+ri)/2;
        int lastplace = -1;
        CHT st;
        st.addline({0, 0}, 0);
        for(int i = 1; i <= m; i++){
            if(last[i] > -1){
                pair<int, int> newline;
                newline = make_pair(-2*last[i], last[i]*last[i]);
                if(last[i] < lastplace) newline.second -= (lastplace - last[i]) * (lastplace - last[i]);
                if(lastplace > -1) newline.second += dp[lastplace];
                st.addline(newline, cnt[lastplace]);
            }
            if(last[i] == -1){
                dp[i] = dp[i-1]; cnt[i] = cnt[i-1];
            }
            else{
                pair<int, int> sus = st.bestval(i);
                dp[i] = i*i + sus.first + lambd;
                cnt[i] = sus.second+1;
                lastplace = i;
            }
            //cout<<"A"<<i<<" "<<dp[i]<<" "<<cnt[i]<<endl;
        }
        if(cnt[m] <= k){
            ri = lambd-1;
            ans = dp[m];
            lamdaval = lambd;
    //cout<<lamdaval<<" "<<ans<<" "<<cnt[m]<<endl;
        }
        else{
            le = lambd+1;
        }
        //cout<<lambd<<" "<<cnt[m]<<endl;
        //return 0;
    }
    return ans - k*lamdaval;
}
/*signed main()
{
    cout<<take_photos(5, 6, 4, {0, 1, 2, 3, 4}, {1, 2, 3, 4, 5});
}*/

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:98:19: warning: 'lamdaval' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     return ans - k*lamdaval;
      |                  ~^~~~~~~~~

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