Submission #1156122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156122		Samuraj	Aliens (IOI16_aliens)	C++20	4 / 100	1 ms	332 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi; 
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;

const int max_n = 1e5+7;
const ll INF = 1e12+7;
const ll INF2 = 1'000'000'000'007;

struct seg{
    ll beg;
    ll end;
    ll a;
    ll b;
    ll k;
};

pl arr[max_n];
ll odj[max_n]; //stale!
ll dp[max_n];
ll val_k[max_n];

vector<pi> points; //do pierwszego sortu!

vector<seg> vec;
void calc_ans(ll n, ll eps){
    //cout << "\n\ncalc ans od eps: " << eps << '\n';
    for(ll i = 1; i <= n; i++){
        //dodanie naszego el!
        ll a = -2*(arr[i].st-1); ll b = (arr[i].st-1)*(arr[i].st-1)+dp[i-1]-odj[i];
        //cout << "\ni: " << i << " a: " << a << " b: " << b << '\n';
        //cout << "arr: " << arr[i].st << ' ' << arr[i].nd << '\n';
        while(1){
            if(vec.empty()){
                vec.pb({-INF,INF,a,b,0});
                break;
            }
            ll up = vec.back().b-b; ll down = a-vec.back().a;
            ll x = up/down; if(up%down != 0) x++;
            //cout << "x: " << x << '\n';
            if(x <= vec.back().beg){
                vec.pop_back();
                continue;
            }
            //dodajemy nasz
            vec[vec.size()-1].end = x-1; 
            vec.pb({x,INF,a,b,val_k[i-1]});
            break;
        }

        //teraz szukamy najlepszego punktu
        ll l = 0; ll r = vec.size()-1; ll ind = 0;
        while(l <= r){
            ll s = (l+r+1)/2;
            //cout << "s: " << s << " beg: " << vec[s].beg << " end: " << vec[s].end << '\n';
            if(vec[s].beg <= arr[i].nd && vec[s].end >= arr[i].nd){
                ind = s;
                break;
            }
            else if(vec[s].end < arr[i].nd) l = s+1;
            else r = s-1;
        }

        //mamy ind!!!
        val_k[i] = vec[ind].k+1;
        dp[i] = arr[i].nd*arr[i].nd+eps+vec[ind].a*arr[i].nd+vec[ind].b;
        //cout << "ind: " << ind << " ind_a: " << vec[ind].a << " ind_b: " << vec[ind].b << '\n'; 
        //cout << "dp: " << dp[i] << " k: " << val_k[i] << '\n';
    }
    vec.clear(); //to wazne
}

ll take_photos(int n, int m, int k, vi row, vi col){
    //ustawic nowe n!
    rep(i,0,n-1){
        if(col[i] < row[i]){
            //przestawienie na gorna polowe!
            int diff = row[i]-col[i];
            col[i] += diff;
            row[i] -= diff;
        }
        points.pb({row[i],col[i]});
    }
    sort(points.begin(),points.end());

    int akt_ind = 0;
    ll max_c = -1;
    rep(i,0,n-1){
        if(points[i].nd <= max_c) continue; //jest dalej mniejsze h!
        if(i != n-1 && points[i+1].st == points[i].st) continue; //ten sam rząd
        arr[++akt_ind] = points[i];
        max_c = points[i].nd;
    }

    //policzyc odj!
    rep(i,2,akt_ind){
        if(arr[i].st > arr[i-1].nd) continue;
        ll val = arr[i-1].nd-arr[i].st+1;
        odj[i] = val*val;
    }

    //rep(i,1,akt_ind)
        //cout << "i: " << i << " arr: " << arr[i].st << ' ' << arr[i].nd << " odj: " << odj[i] << '\n';

    k = min(k,akt_ind); //wazne, zeby za duzo prostokatow nie robic!!!

    ll l = 0; ll r = INF; ll ans = 0;
    while(l <= r){
        ll s = (l+r+1)/2;
        calc_ans(akt_ind,s);
        if(val_k[akt_ind] <= k){
            ans = dp[akt_ind]-ll(k)*s;
            r = s-1;
        }
        else l = s+1; //zwiekszam kare
    }
    ////cout << "ans: " << ans << '\n';

    return ans;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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