Submission #636166

#	Time	Username	Problem	Language	Result	Execution time	Memory
636166		ionan6ix	Aliens (IOI16_aliens)	C++17	4 / 100	6 ms	724 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;

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);
    }
    n = obj.size();
    vector<long long> dp;
    vector<int> pics;
    dp.resize(n+1);
    pics.resize(n+1);

    LineContainer lc;

    lc.add(2*obj[1].first,-obj[1].first*obj[1].first);
    M[make_pair(2*obj[1].first,-obj[1].first*obj[1].first)] = 0;

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

        Line best = lc.getLine(zi);
        long long res = -lc.query(zi);

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

        pics[i] = 1 + M[make_pair(best.k,best.m)];

        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;

        lc.add(a,b);

        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 = 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 function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:139:29: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
  139 |     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