Submission #199160

#	Time	Username	Problem	Language	Result	Execution time	Memory
199160		Ruxandra985	Aliens (IOI16_aliens)	C++14	60 / 100	2016 ms	53368 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#define DIMN 100010
#define INF 2000000000000000000
using namespace std;
pair <int,int> v[DIMN];
long long dp[DIMN];
int cnt[DIMN];
struct lichao{
    long long x , y ;
    int nr;
} aint[4000010];
int cmp (pair <int,int> x , pair <int,int> y){
    if (x.first != y.first)
        return x.first < y.first;
    return x.second > y.second;
}
void update (int nod,int st,int dr,long long x,long long y , int nr){
    if (st == dr){
        if (1LL * aint[nod].x * st + aint[nod].y > 1LL * x * st + y){
            aint[nod].x = x;
            aint[nod].y = y;
            aint[nod].nr = nr;
        }
        return;
    }
    long long mid = ((st + dr) >> 1),st1=0,st2=0;
    if (1LL * aint[nod].x * mid + aint[nod].y > 1LL * x * mid + y)
        st1 = 1;
    if (1LL * aint[nod].x * dr + aint[nod].y > 1LL * x * dr + y)
        st2 = 1;

    if (!st1 && !st2){
        update ((nod << 1),st,mid,x,y , nr);
    }
    else if (!st1 && st2) {
        update (((nod << 1) | 1),mid+1,dr,x,y , nr);
    }
    else if (st1 && !st2){
        swap(x,aint[nod].x);
        swap(y,aint[nod].y);
        swap(nr , aint[nod].nr);
        update (((nod << 1) | 1),mid+1,dr,x,y , nr);
    }
    else if (st1 && st2){
        swap(x,aint[nod].x);
        swap(y,aint[nod].y);
        swap(nr , aint[nod].nr);
        update ((nod << 1),st,mid,x,y , nr);
    }

}
pair <long long  , int> query (long long nod,long long st,long long dr,int x){
    if (st==dr){
        return make_pair( 1LL * aint[nod].x * x + aint[nod].y , 1 + aint[nod].nr);
    }
    long long mid = ((st + dr) >> 1);
    pair <long long , int> sol = make_pair(INF , 0);
    if (x<=mid)
        sol = query((nod << 1),st,mid,x);
    else sol = query(((nod << 1) | 1),mid+1,dr,x);
    if (sol.first < 1LL * aint[nod].x * x + aint[nod].y || (sol.first == 1LL * aint[nod].x * x + aint[nod].y && sol.second < aint[nod].nr + 1))
        return sol;
    else{
        sol = make_pair(1LL * aint[nod].x * x + aint[nod].y , 1 + aint[nod].nr);
        return sol;
    }
}
void build (long long nod,long long st,long long dr){
    int mid = ((st + dr) >> 1);

    aint[nod].x = aint[nod].y = 1000000000000;

    if (st == dr)
        return;

    build ((nod << 1),st,mid);
    build (((nod << 1) | 1),mid+1,dr);

}
pair <long long,long long> solve (long long x , int n , int m){ /// cost x , n intervale
    long long i , aux;
    pair <long long , long long> p;
    build (1, 1, m);
    for (i = 1 ; i <= n ; i++){
        aux = max (0LL , ((long long)v[i-1].second - v[i].first + 1));
        update(1 , 1 , m ,-2LL * v[i].first , dp[i-1] + 1LL * v[i].first * (v[i].first - 2) - 1LL * aux * aux , cnt[i-1]);
        p = query(1 , 1 , m , v[i].second); /// VREAU MINIMUL DE AICI , merge cu li chao??
        dp[i] = p.first + 1LL * v[i].second * v[i].second + 2LL * v[i].second + x + 1;
        cnt[i] = p.second;
    }
    return make_pair(cnt[n] , dp[n]);

}
long long take_photos (int n , int m , int k , vector <int> r , vector <int> c){
    long long st , dr , mid;
    int i , n2 , rm;
    pair <long long,long long> rez;
    for (i=0;i<n;i++){
        v[i+1] = make_pair(r[i] + 1 , c[i] + 1);
        if (v[i+1].first > v[i+1].second)
            swap (v[i+1].first , v[i+1].second);
        v[i+1].second = -v[i+1].second;
    }
    sort (v + 1 , v + n + 1);
    n2 = 0;
    rm = 0;
    for (i=1;i<=n;i++){ /// nu iau intervale incluse total unul in altul
        v[i].second = -v[i].second;
        if (rm < v[i].second)
            v[++n2] = v[i];
        rm = max(rm , v[i].second);
    }
    n = n2;
    if (n <= k)
        return solve (0 , n2 , m).second;
    st = 0;
    dr = 1152921504606846976;
    while (st <= dr){
        mid = ((st + dr) >> 1);
        rez = solve(mid , n2 , m);
        if (rez.first > k)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    rez = solve(st , n2 , m);
    return rez.second - st * k;

}

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