Submission #199161

#	Time	Username	Problem	Language	Result	Execution time	Memory
199161		Ruxandra985	Aliens (IOI16_aliens)	C++14	100 / 100	1683 ms	70548 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 , last;
    int nr;
} aint[4000010];
void update (int nod,int st,int dr,long long x,long long y , int nr , long long last){
    if (st == dr){
        if (1LL * aint[nod].x * st + aint[nod].y > 1LL * x * st + y || aint[nod].last != last){
            aint[nod].x = x;
            aint[nod].y = y;
            aint[nod].nr = nr;
            aint[nod].last = last;
        }
        return;
    }
    long long mid = ((st + dr) >> 1),st1=0,st2=0;
    if (1LL * aint[nod].x * mid + aint[nod].y > 1LL * x * mid + y || aint[nod].last != last)
        st1 = 1;
    if (1LL * aint[nod].x * dr + aint[nod].y > 1LL * x * dr + y || aint[nod].last != last)
        st2 = 1;

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

}
pair <long long  , int> query (long long nod,long long st,long long dr,int x , long long last){
    if (st==dr){
        if (aint[nod].last == last)
            return make_pair( 1LL * aint[nod].x * x + aint[nod].y , 1 + aint[nod].nr);
        else return make_pair(INF , 1);
    }
    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 , last);
    else sol = query(((nod << 1) | 1),mid+1,dr,x , last);
    if (aint[nod].last != last || (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{
        if (aint[nod].last == last)
            sol = make_pair(1LL * aint[nod].x * x + aint[nod].y , 1 + aint[nod].nr);
        return sol;
    }
}
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;
    /// daca last != x , te prefaci ca valoarea e mai mare
    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] , x);
        p = query(1 , 1 , m , v[i].second , x); /// 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: 40 / 40