Submission #637897

#	Time	Username	Problem	Language	Result	Execution time	Memory
637897		ionan6ix	Aliens (IOI16_aliens)	C++17	4 / 100	2 ms	340 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>

using namespace std;

#pragma once
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};

map<pair<ll,ll>,int > M;

using ll = long long;
using pli = pair<ll, int>;
using pii = pair<int, int>;
#define F first
#define S second

struct CHT {
    struct line {
        ll m, c;
        int cnt;
        line(ll m, ll c, int cnt) : m(m), c(c), cnt(cnt) {}
        ll get(ll x) { return m*x + c; }
    };
    bool bad(line l1, line l2, line l3) {
        return (l3.c-l1.c)*(l1.m-l2.m) <= (l2.c-l1.c)*(l1.m-l3.m);
    }
    vector<line> f;
    int idx;
    void update(ll m, ll c, int cnt) {
        line l(m, c, cnt);
        while (f.size() > 1 && bad(f[f.size()-2], f[f.size()-1], l))
            f.pop_back();
        f.push_back(l);
    }
    pli query(ll x) {
        idx = min(idx, (int)f.size()-1);
        while (idx < f.size()-1 && f[idx].get(x) > f[idx+1].get(x))
            ++idx;
        return pli(f[idx].get(x), f[idx].cnt);
    }
    void clear() {
        f.clear();
        idx = 0;
    }
} cht;

struct LineContainer : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    static const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) return x->p = inf, 0;
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }

    Line getLine(ll x)
    {
        assert(!empty());
        auto l = *lower_bound(x);
        return l;
    }
};

bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
    if(a.first==b.first)
        return a.second>b.second;

    return a.first<b.first;
}

bool inters(pair<int,int> a,pair<int,int> b)
{
    if(a.first<=b.first && a.second>=b.second)
        return true;
    return false;
}

pair<ll,ll> pics(long long penalty,int n,int m,vector<int>& r,vector<int>& c)
{
    vector<pair<long long,long long> > obj;
    vector<pair<long long,long long> > aux;
    for(int i = 0;i<n;i++)
        aux.emplace_back(1LL*min(r[i],c[i]),1LL*max(r[i],c[i]));

    sort(aux.begin(),aux.end(),cmp);

    obj.emplace_back(-1,-1);

    for(auto it:aux)
    {
        if(!inters(obj.back(),it))
            obj.push_back(it);
    }

    M.clear();
    n = obj.size();
    vector<long long> dp;
    vector<int> pics;
    dp.resize(n+1);
    pics.resize(n+1);

   // LineContainer lc;
    //lc.clear();

    cht.clear();

    cht.update(-2*obj[1].first,-(-dp[0]-obj[1].first*obj[1].first),0);
   // M[make_pair(2*obj[1].first,-dp[0]-obj[1].first*obj[1].first)] = 0;

    for(int i=1;i<n;i++)
    {
        long long zi = obj[i].second+1;

        pair<long long,int> best = cht.query(zi);
        long long res = best.first;

        dp[i] = res + zi * zi + penalty;

        pics[i] = 1 + best.second;
        if(i==(n-1)) continue;

        long long intersection = max(0LL,obj[i].second-obj[i+1].first+1LL)*max(0LL,obj[i].second-obj[i+1].first+1LL);
        long long a = 2 * obj[i + 1].first;
        long long b = -dp[i] - obj[i + 1].first * obj[i + 1].first + intersection;

        cht.update(-a,-b,pics[i]);

        //lc.add(-a,-b,pics[i]);

    //    M[make_pair(a,b)] = pics[i];
    }

    return make_pair(dp[n-1],pics[n-1]);

}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {

    long long st = 0;
    long long dr = 1LL*m*m;
    long long sol;
    pair<ll,ll> best;

    while(st<=dr)
    {
        long long mid = (st+dr)>>1;

        if(pics(mid,n,m,r,c).second<=k)
        {
            sol=mid;
            best = pics(mid,n,m,r,c);
            dr = mid-1;
        }
        else st = mid+1;

    }

    return best.first - sol * best.second;
}

Compilation message (stderr)

aliens.cpp:6:9: warning: #pragma once in main file
    6 | #pragma once
      |         ^~~~
aliens.cpp: In member function 'pli CHT::query(ll)':
aliens.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CHT::line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         while (idx < f.size()-1 && f[idx].get(x) > f[idx+1].get(x))
      |                ~~~~^~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:183:29: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
  183 |     return best.first - sol * best.second;
      |                         ~~~~^~~~~~~~~~~~~

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