Submission #172869

#	Time	Username	Problem	Language	Result	Execution time	Memory
172869		Mercenary	Aliens (IOI16_aliens)	C++14	100 / 100	217 ms	15480 KiB

aliens

#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair
#ifndef LOCAL
#include "aliens.h"
#endif // LOCAL
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll,ll> ii;
const int maxn = 2e5 +5;
const int logn = 20;

struct point{
    ld x , y;
    point(){};
    point(ld x , ld y):x(x) , y(y){};
    point operator - (const point & other){
        return point(x - other.x , y - other.y);
    }
    ld operator * (const point & other){
        return x * other.y - y * other.x;
    }
};
pair<point,int> a[maxn];
ii b[maxn];
ll dp[maxn];
int cnt[maxn];
ll sqr(ll x){
    return x * x;
}
void Solve(int n , ll val){
    int m = 0 , p = 1;
    b[0] = mp(-1,-1);
    for(int i = 1 ; i <= n ; ++i){
        auto add = [&](pair<point,int> x){
            while(m >= 2 && (a[m - 1].first - a[m].first) * (x.first - a[m].first) <= 0){
                if(p == m)--p;
                --m;
            }
            a[++m] = x;
        };
        add(mp(point(-2*b[i].first,sqr(b[i].first)+dp[i - 1]-sqr(max(0ll,b[i-1].second-b[i].first+1))),i-1));
        while(p < m && a[p].first.x * (b[i].second + 1) + a[p].first.y >
              a[p + 1].first.x * (b[i].second + 1) + a[p + 1].first.y)++p;
        cnt[i] = cnt[a[p].second] + 1;
        dp[i] = a[p].first.x * (b[i].second + 1) + a[p].first.y + sqr(b[i].second + 1) + val;
    }
}

long long take_photos(int n, int m, int k,vector<int> r, vector<int> c) {
    for(int i = 0 ; i < n ; ++i){
        if(r[i] < c[i])swap(r[i],c[i]);
        b[i + 1] = mp(r[i] , c[i]);
    }
    sort(b + 1 , b + n + 1 , [&](const ii x , const ii y){
            if(x.first != y.first)return x.first < y.first;
            return x.second > y.second;
         });
    int cnt = 0;
    for(int i = 1 ; i <= n ; ++i){
        while(cnt > 0 && b[cnt].second >= b[i].second)--cnt;
        b[++cnt] = b[i];
    }
    for(int i = 1 ; i <= n ; ++i)swap(b[i].first,b[i].second);
    n = cnt;
//    for(int i = 1 ; i <= n ; ++i)cout << b[i].first << " " << b[i].second << endl;
    ll l = 0 , h = (ll)(m + 1) * (m + 1);
    while(l <= h){
        ll mid = l + h >> 1;
        Solve(n , mid);
        if(::cnt[n] > k)l = mid + 1;
        else h = mid - 1;
    }
    Solve(n,l);
//    cout << ::cnt[n] << endl;
    return dp[n] - (ll)k * l;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:76:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mid = l + h >> 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