Submission #201841

#	Time	Username	Problem	Language	Result	Execution time	Memory
201841		anonymous	Aliens (IOI16_aliens)	C++14	100 / 100	156 ms	11620 KiB

aliens

#include "aliens.h"
#include<vector>
#include<utility>
#include<algorithm>
#define LL long long
#define MAXN 100005
using namespace std;

class CHT {
    vector<pair<pair<LL,LL>, int> > S;
    int pt=0;
public:
    void reset() {
        S.clear();
        pt=0;
    }
    bool bad(LL mq, LL cq, LL num) { //min number of photo
        LL m2=S[S.size()-2].first.first, c2=S[S.size()-2].first.second;
        LL m1=S.back().first.first, c1=S.back().first.second;
        if ((c1-c2)*(m2-mq) != (cq-c2)*(m2-m1)) {
            return((c1-c2)*(m2-mq) > (cq-c2)*(m2-m1));
        }
        return(S.back().second > num);
    }
    void put(LL m, LL c, LL num) {
        while (S.size() > 1 && bad(m,c,num)) {
            S.pop_back();
            pt=min(pt, (int) S.size()-1);
        }
        S.push_back({{m,c},num});
    }
    pair<LL,LL> eval(int l, LL p) {
         return(pair<LL,LL> {S[l].first.first*p+S[l].first.second, S[l].second});
    }
    pair<LL,LL> ask(LL p) { //returns min value & number of photos
        while (pt<S.size()-1 && eval(pt, p) > eval(pt+1, p)) {pt++;}
        return(eval(pt,p));
    }
} CHT;

vector<pair<LL, LL> > Sweep; //r is first l is second
vector<pair<LL,LL> > SS; //sorted stack to get non-dominated points
LL dp[MAXN][2];

pair<LL,LL> slv(LL C) {
    CHT.reset();
    CHT.put(-2*SS[0].second, SS[0].second*SS[0].second,0);
    for (int i=0; i<SS.size(); i++) {
        pair<LL,LL> res=CHT.ask(SS[i].first);
        dp[i+1][0]=res.first + C + SS[i].first*SS[i].first;
        dp[i+1][1]=res.second + 1;
        if (i+1<SS.size()) {
                LL newm=-2*SS[i+1].second;
                LL newc=dp[i+1][0] + SS[i+1].second*SS[i+1].second;
                if (SS[i+1].second < SS[i].first) {newc-=(SS[i+1].second - SS[i].first)*(SS[i+1].second - SS[i].first);}
                CHT.put(newm, newc, dp[i+1][1]);
        }
    }
    return(pair<LL,LL> {dp[SS.size()][0], dp[SS.size()][1]});
}

LL wqs(LL k) {
    LL lo = 0, hi=1LL<<40;
    k=min(k, (LL) SS.size());
    while (lo + 1 != hi) {
        LL mid=(lo+hi)>>1;
        if (slv(mid).second > k) {
            lo=mid;
        } else {
            hi=mid;
        }
    }
    return(slv(hi).first - k*hi);
}

LL take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for (int i=0; i<n; i++) {
        Sweep.push_back({max(r[i],c[i])+1, -min(r[i],c[i])});
    }
    sort(Sweep.begin(), Sweep.end());
    for (auto p: Sweep) {
        p.second=-p.second;
        while (SS.size() && SS.back().second >= p.second) {SS.pop_back();}
        SS.push_back(p);
    }

    return(wqs(k));
}

Compilation message (stderr)

aliens.cpp: In member function 'std::pair<long long int, long long int> CHT::ask(long long int)':
aliens.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (pt<S.size()-1 && eval(pt, p) > eval(pt+1, p)) {pt++;}
                ~~^~~~~~~~~~~
aliens.cpp: In function 'std::pair<long long int, long long int> slv(long long int)':
aliens.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<SS.size(); i++) {
                   ~^~~~~~~~~~
aliens.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i+1<SS.size()) {
             ~~~^~~~~~~~~~

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