Submission #1119319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119319		epicci23	Aliens (IOI16_aliens)	C++17	25 / 100	279 ms	94616 KiB

aliens

#include "bits/stdc++.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;

const ll N = (ll) 1e6 + 5;
const ll INF = (ll) 1e18 + 5;
const ll INF2 = (ll) 1e9 + 5;

vector<array<ll,2>> v;

struct Line{
   ll sl,cn,tag;
   inline void Set_Line(ll _a,ll _b, ll _tag){sl = _a, cn = _b, tag = _tag;}
   inline ll get_val(ll _x){return _x * sl + cn;}
};

struct LiChao{
   vector<Line> seg;
   LiChao(ll _m){
   	 seg.resize(4 * _m + 5);
   	 for(int i = 0 ; i < 4 * _m + 5 ; i++) seg[i].Set_Line(0, INF, 0);
   }
   void add(ll rt, ll l, ll r, Line u){
     ll mid = (l + r) / 2;
     if(u.get_val(mid) < seg[rt].get_val(mid)) swap(seg[rt], u);
     if(u.get_val(mid) == seg[rt].get_val(mid) && u.tag < seg[rt].tag) swap(seg[rt], u);
     if(l == r) return;
     if(u.sl > seg[rt].sl) add(rt * 2, l, mid, u);
     else add(rt * 2 + 1, mid + 1, r, u);
   }
   Line get_min(ll rt, ll l, ll r, ll ind){
     if(l == r) return seg[rt];
     Line res = seg[rt] , curi;
     ll mid = (l + r) / 2;

     if(ind <= mid) curi = get_min(rt * 2, l, mid, ind);
     else curi = get_min(rt * 2 + 1, mid + 1, r, ind);

     if(curi.get_val(ind) < res.get_val(ind)) swap(curi,res);
     if(curi.get_val(ind) == res.get_val(ind) && curi.tag < res.tag) swap(curi, res);
     return res; 
   }
};

LiChao T(N);

array<ll,2> wqs_binary_search(ll lambda){
  ll n = sz(v) - 1;
  vector<ll> dp(n+5,INF),Use(n+5,INF);
  Use[0] = dp[0] = 0;
  
  for(int i = 0 ; i < 4 * N + 5; i++) T.seg[i].Set_Line(0 , INF, 0);
  
  Line ekle;
  ekle.Set_Line(-2 * v[1][0], v[1][0] * v[1][0], 0);
  T.add(1,1,N,ekle);
  
  for(int i = 1; i <= n ; i++){
    ll a = v[i][0] , b = v[i][1] + 1;
    //cout << "point: " << a << ' ' << b << '\n';
    Line Gel = T.get_min(1, 1, N, b);
    dp[i] = Gel.get_val(b) + b * b + lambda;
    Use[i] = Gel.tag + 1;
    //cout << i << ' ' << dp[i] << ' ' << Use[i] << '\n';
    if(i < n){
     Line ekle2;
     ekle2.Set_Line(-2 * v[i + 1][0], dp[i] + v[i + 1][0] * v[i + 1][0] 
     	- max(0LL,b - v[i + 1][0]) * max(0LL,b - v[i + 1][0]), Use[i]);
     T.add(1,1,N,ekle2);
    }
  }

  return {dp[n],Use[n]};
}


ll take_photos(int _n,int _m,int _k,vector<int> r,vector<int> c){
  ll n = _n, m = _m, k = _k;

  for(ll i=0;i<n;i++){
  	ll a = r[i], b = c[i];
  	if(a > b) swap(a, b);
  	v.push_back({a,b});
  }	

  sort(all(v));
  vector<array<ll,2>> xdd;
  xdd.push_back({-1LL, -1LL});
  for(ll i = 0; i < n; i++){
  	if(v[i][0] == xdd.back()[0]){
  	  xdd.pop_back();
  	  xdd.push_back(v[i]);
  	}
  	else if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
  }  
  swap(v,xdd);
  ll res_l = 0, res_r = INF2;

  while(res_l < res_r){
    ll lol = (res_l+res_r)/2;
    array<ll,2> hmm = wqs_binary_search(lol);
    if(hmm[1] > k) res_l = lol + 1;
    else res_r = lol;
  }
   
  array<ll,2> ANS = wqs_binary_search(res_l);
  return ANS[0] - res_l * k;
}

/*void _(){
  int n,m,k;
  cin >> n >> m >> k;
  for(int i = 0; i < n; i++){
  	int a,b;
  	cin >> a >> b;
  	if(a>b) swap(a,b);
  	v.push_back({a,b});
  }

  sort(all(v));
  vector<array<ll,2>> xdd;
  xdd.push_back({-1LL, -1LL});
  for(int i=0;i<n;i++){
  	if(v[i][0] == xdd.back()[0]){
  	  xdd.pop_back();
  	  xdd.push_back(v[i]);
  	}
  	else if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
  }  
  swap(v,xdd);
  ll res_l = 0, res_r = INF2;

  while(res_l < res_r){
    ll lol = (res_l+res_r)/2;
    array<ll,2> hmm = wqs_binary_search(lol);
    if(hmm[1] > k) res_l = lol + 1;
    else res_r = lol;
  }
  
  //cout << "penalty: " << res_l << '\n';
  array<ll,2> ANS = wqs_binary_search(res_l);
  //cout << ANS[0] << ' ' << ANS[1] << '\n';
  cout <<  ANS[0] - res_l * k << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

Compilation message (stderr)

aliens.cpp: In function 'std::array<long long int, 2> wqs_binary_search(long long int)':
aliens.cpp:61:8: warning: unused variable 'a' [-Wunused-variable]
   61 |     ll a = v[i][0] , b = v[i][1] + 1;
      |        ^
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:80:14: warning: unused variable 'm' [-Wunused-variable]
   80 |   ll n = _n, m = _m, k = _k;
      |              ^

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