Submission #935031

#	Time	Username	Problem	Language	Result	Execution time	Memory
935031		dimashhh	Aliens (IOI16_aliens)	C++17	100 / 100	799 ms	24552 KiB

aliens

#include <bits/stdc++.h>
 #include<aliens.h>
using namespace std;
 
const int N = 1e6 + 3, MOD = 1e9 + 7;
 
typedef long long ll;
 
int n,m,k;
vector<pair<ll,ll>> a,x;
ll res;
ll dp[N],L[N],R[N];
int col[N];
struct line{
    ll k,b;
    int id;
    ll calc(ll x){
        return k * x + b;
    }
};
vector<line> st;
long double cross(line x,line y){
    return (long double)(x.b - y.b) / (long double)(y.k - x.k);
}
void add(line nv){
    int m = (int)st.size();
    while(st.size() > 1 && cross(nv,st[m - 1]) <= cross(st[m - 1],st[m - 2])){
        st.pop_back();
        m--;
    }
    st.push_back(nv);
}
pair<int,ll> get(ll x){
    int l = -1,r = (int)st.size() - 1;
    while(r - l > 1){
        int mid = (l + r) >> 1;
        if(cross(st[mid],st[mid + 1]) > (long double)x){
            r = mid;
        }else{
            l = mid;
        }
    }
    ll mn = 1e18;
    int ret = 1e9;
    for(auto j:st){
        if(j.calc(x) <= mn){
            mn = j.calc(x);
            ret = j.id;
        }
    }
//    if(st[r].id != ret) {
//        cout << st[r].id << ' ' << ret << "x\n";
//        cout << x << '\n';
//        for(int i = 0;i < (int)st.size() - 1;i++){
//            cout << cross(st[i],st[i + 1]) << ' ';
//        }
//        cout << '\n';
//        for(auto j:st){
//            cout << j.id << ' ';
//        }
//        cout << '\n';
//
//        exit(0);
//    }
    return {st[r].id,st[r].calc(x)};
}
ll f(ll pen){
    st.clear();
    dp[0] = 0;
    col[0] = 0;
    for(int i = 1;i <= n;i++){
        add({-L[i], dp[i - 1] + L[i] * L[i] - max(R[i - 1] - L[i], 0ll) * max(0ll, R[i - 1] - L[i]) + pen,i});
        pair<int,ll> g = get(2 * R[i]);
        dp[i] = g.second + R[i] * R[i];
        col[i] = col[g.first - 1] + 1;
    }
    res = dp[n];
    return col[n];
}
long long take_photos(int nn,int mm,int kk,vector<int> rr,vector<int> cc){
    n = nn;
    m = mm;
    k = kk;
    for(int i = 1;i <= n;i++){
        int l = rr[i - 1],r = cc[i - 1];
        ++l;++r;
        if(l > r){
            swap(l,r);
        }
        a.push_back({l,-r});
    }
    sort(a.begin(),a.end());
    int mx = 0;
    x.push_back({0,0});
    for(auto [l,r]:a){
        r = -r;
        if(r > mx){
            mx = r;
            x.push_back({l,r});
        }
    }
    sort(x.begin(),x.end());
    n = (int)x.size() - 1;
    for (int i = 1; i <= n; i++) {
        L[i] = x[i].first - 1;
        R[i] = x[i].second;
    }
    ll l = -1,r = 1e15;
    k = min(k,n);
    while(r - l > 1) {
        ll mid = (l + r) >> 1;
        if (f(mid) >= k) {
            l = mid;
        } else {
            r = mid;
        }
    }
    ll x = f(l);
    return res - k * 1ll * l;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<int, long long int> get(ll)':
aliens.cpp:44:9: warning: variable 'ret' set but not used [-Wunused-but-set-variable]
   44 |     int ret = 1e9;
      |         ^~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:118:8: warning: unused variable 'x' [-Wunused-variable]
  118 |     ll x = f(l);
      |        ^

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