Submission #1034476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034476		Wansur	Aliens (IOI16_aliens)	C++14	100 / 100	397 ms	64572 KiB

aliens

#include <bits/stdc++.h>
#define ent '\n'
#define f first
#define s second

typedef long long ll;
using namespace std;
const int maxn = 1e6+12;

pair<ll, int> dp[maxn];
vector<int> g[maxn];
bool was[maxn];
vector<int> t;
int L[maxn];
int R[maxn];
int n, m;

struct line{
    ll k, b;
    int c;
};

bool check(line nw, line last, line prl){
    if((nw.b - prl.b) * (prl.k - last.k) <= (last.b - prl.b) * (prl.k - nw.k))return 1;
    return 0;
}

int ptr = 0;
vector<line> l;

void add(line x){
    while(l.size() && l.back().k == x.k && l.back().b > x.b){
        l.pop_back();
    }
    if(l.size() && l.back().k == x.k && l.back().b <= x.b){
        return;
    }
    while(l.size()>1 && check(x, l.back(), l[l.size()-2])){
        l.pop_back();
    }
    l.push_back(x);
}

pair<ll, int> get(ll x){
    if(!l.size()){
        return {1e18, 1e9};
    }
    if(ptr >= l.size()){
        ptr = l.size()-1;
    }
    while(ptr + 1 < l.size() && l[ptr].k * x + l[ptr].b > l[ptr+1].k * x + l[ptr+1].b){
        ptr++;
    }
    while(ptr - 1 >= 0 && l[ptr].k * x + l[ptr].b > l[ptr-1].k * x + l[ptr-1].b){
        ptr--;
    }
    return {l[ptr].k * x + l[ptr].b, l[ptr].c + 1};
}

int check(ll k){
    add({0, 0, 0});
    for(int &i:t){
        dp[i] = get(i);
        dp[i].f += i * 1ll * i + k;
        for(int &j:g[i]){
            ll b = j * 1ll * j + dp[R[j]].f, c = dp[R[j]].s;
            if(R[j] > j) b -= (R[j] - j) * 1ll * (R[j] - j);
            add({-2 * j, b, c});
        }
    }
    l.clear();
    ptr = 0;
    return dp[m].s;
}

long long take_photos(int N, int M, int k, vector<int> r, vector<int> c){
    n = N, m = M;
    for(int i=1;i<=m;i++){
        L[i] = 1e9;
    }
    m = 0;
    for(int i=0;i<n;i++){
        if(r[i] < c[i]){
            swap(r[i], c[i]);
        }
        r[i]++, c[i]++;
        L[r[i]] = min(L[r[i]], c[i]);
        R[c[i]] = max(R[c[i]], r[i]);
        for(int x=-1;x<=0;x++){
            was[r[i]+x] = was[c[i]+x] = 1;
        }
        m = max(m, r[i]);
    }
    was[1] = 1;
    for(int i=1;i<=m;i++){
        R[i] = max(R[i], R[i-1]);
        if(!was[i]) continue;
        t.push_back(i);
        g[max(R[i], i)].push_back(i);
    }
    ll val = 1e13;
    for(ll l = 0, r = 1e13; l <= r;){
        ll mid = l + r >> 1;
        if(check(mid) <= k){
            val = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    check(val);
    return dp[m].f - k * val;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, int> get(ll)':
aliens.cpp:48:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     if(ptr >= l.size()){
      |        ~~~~^~~~~~~~~~~
aliens.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while(ptr + 1 < l.size() && l[ptr].k * x + l[ptr].b > l[ptr+1].k * x + l[ptr+1].b){
      |           ~~~~~~~~^~~~~~~~~~
aliens.cpp: In function 'int check(ll)':
aliens.cpp:68:29: warning: narrowing conversion of 'c' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   68 |             add({-2 * j, b, c});
      |                             ^
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:103:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |         ll mid = l + r >> 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