Submission #885009

#	Time	Username	Problem	Language	Result	Execution time	Memory
885009		epicci23	Aliens (IOI16_aliens)	C++17	4 / 100	331 ms	94548 KiB

aliens

#include "aliens.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const ll M = 1e6 + 5;

struct Line{
  ll mx,b,ind;
  ll get(int x){return mx*x+b;}
}seg[4*M];

vector<array<ll,2>> v;
vector<ll> intr;


Line query(int rt,int l,int r,int u){
  if(l==r) return seg[rt];
  int m=(l+r)/2;
  if(u<=m){
    if(seg[rt*2].ind==-1) return seg[rt];
    Line left = query(rt*2,l,m,u);
    if(left.get(u)<seg[rt].get(u)) return left;
    else return seg[rt];
  }
  else{
    if(seg[rt*2+1].ind==-1) return seg[rt];
    Line right = query(rt*2+1,m+1,r,u);
    if(right.get(u)<seg[rt].get(u)) return right;
    else return seg[rt];
  }
}

void upd(int rt,int l,int r,Line cur){
  if(seg[rt].ind==-1){
     seg[rt]=cur;
     return;
  }
  int m=(l+r)/2;
  if(cur.get(m)<seg[rt].get(m)) swap(seg[rt],cur);
  if(l==r) return;
  if(seg[rt].mx<=cur.mx) upd(rt*2,l,m,cur);
  else upd(rt*2+1,m+1,r,cur);
}

 
array<ll,2> f(int lambda){
 int N = sz(v);
 ll dp[N+5],cnt[N+5];
 cnt[0]=dp[0]=0;
 for(int i=0;i<4*M;i++) seg[i].mx=seg[i].b=seg[i].ind=-1; 

 for(int i=1;i<=N;i++){
   Line xd; xd.ind=i-1;
   xd.mx=-2*v[i-1][0]; xd.b=dp[i-1]-intr[i-1]+v[i-1][0]*v[i-1][0];
   upd(1,1,M-1,xd);
   ll xx = v[i-1][1]+1;
   Line qq = query(1,1,M-1,xx);
   dp[i] = xx*xx + lambda + qq.get(xx);
   cnt[i]=cnt[qq.ind]+1;
 }

 return {dp[N],cnt[N]};
}


ll take_photos(int n,int m,int k, vector<int> r, vector<int> c){
  for(int i=0;i<n;i++) if(r[i]>c[i]) swap(r[i],c[i]);
  for(int i=0;i<n;i++) v.pb({r[i],c[i]});
  sort(all(v));
  vector<array<ll,2>> cur;
  for(int i=0;i<n;i++){ 
    while(!cur.empty() && cur.back()[0]==v[i][0]) cur.pop_back();
    if(cur.empty() || v[i][1]>cur.back()[1]) cur.pb(v[i]);
  }
  swap(v,cur);
  
  intr.resize(sz(v)+5);
  intr[0]=0;
  for(int i=1;i<sz(v);i++) intr[i]=max(v[i-1][1]-v[i][0]+1,0LL)*max(v[i-1][1]-v[i][0]+1,0LL);
  
  ll bl=0,br=(ll)1e12;
  while(bl<br){
    ll mid=(bl+br)/2;
    if(f(mid)[1]>k) bl=mid+1;
    else br=mid;
  }

  return f(bl)[0]-k*bl;
}

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