제출 #199152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199152		Ruxandra985	Aliens (IOI16_aliens)	C++14	4 / 100	5 ms	380 KiB

aliens

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

    if (!st1 && !st2){
        update (2*nod,st,mid,x,y , nr);
    }
    else if (!st1 && st2) {
        update (2*nod+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 (2*nod+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 (2*nod,st,mid,x,y , nr);
    }

}
pair <long long  , long long> query (long long nod,long long st,long long dr,long long x){
    if (st==dr){
        return make_pair( aint[nod].x * x + aint[nod].y , 1 + aint[nod].nr);
    }
    long long mid = (st+dr)/2;
    pair <long long , long long> sol = make_pair(INF , 0);
    if (x<=mid)
        sol = query(2*nod,st,mid,x);
    else sol = query(2*nod+1,mid+1,dr,x);
    if (sol.first < aint[nod].x * x + aint[nod].y || (sol.first == aint[nod].x * x + aint[nod].y && sol.second < aint[nod].nr + 1))
        return sol;
    else{
        sol = make_pair(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)/2;

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

    if (st == dr)
        return;

    build (2*nod,st,mid);
    build (2*nod+1,mid+1,dr);

}
pair <long long,long long> solve (long long x , long long n , long long m){ /// cost x , n intervale
    long long i , aux;
    pair <long long , long long> p;
    build (1, 1, m);
    //if (x == 0)
      //  printf ("a");
    for (i = 1 ; i <= n ; i++){
        aux = max (0LL , (v[i-1].second - v[i].first + 1));
        update(1 , 1 , m ,-2 * v[i].first , dp[i-1] + v[i].first * (v[i].first - 2) - 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 + v[i].second * v[i].second + 2 * 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;
    long long 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);
    }
    sort (v + 1 , v + n + 1 , cmp);
    n2 = 0;
    rm = 0;
    for (i=1;i<=n;i++){ /// nu iau intervale incluse total unul in altul
        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)/2;
        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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40