Submission #567647

#	Time	Username	Problem	Language	Result	Execution time	Memory
567647		gs15120	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	312 KiB

aliens

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <cassert>
#include <thread>
#include <tuple>
#include <typeindex>
  

using namespace std;
#define ll long long
#define lll long long//__int128
#define pii pair<int,int>
#define pdi pair<double,int>
#define f first
#define s second
# define pi 3.14159265358979323846

const ll inf=1987654321987654321;

struct L
{
    ll a,b;
    int n;
    ll sol(ll x)
    {
        return a*x+b;
    }
};
 
struct LI
{
    int x,y;
    L l={0,inf};
};
 
int a,b,c,d;
 
 
int dx[10]={1,0,-1,0,-1,1,-1,1},dy[11]={0,1,0,-1,-1,-1,1,1},sx[4]={0,1,0,1},sy[4]={0,0,1,1};
ll x,y,z,rv,lv;
int o[111111];
bool ck[111111];
 
vector<LI> li;
void add(int i,int n,int m,L l)
{
    int h=(n+m)/2;
    if(l.sol(h)<li[i].l.sol(h))
    {
        swap(l,li[i].l);
    }
    L s=li[i].l;
    if(l.sol(n)<s.sol(n))
    {
        if(!li[i].x)
        {
            li[i].x=li.size();
            li.push_back({});
        }
        add(li[i].x,n,h,l);
    }
    if(l.sol(m)<s.sol(m))
    {
        if(!li[i].y)
        {
            li[i].y=li.size();
            li.push_back({});
        }
        add(li[i].y,h+1,m,l);
    }
}
 
L get(int i,int n,int m,int k)
{
    if(!i||m<k||n>k) return {0,inf,0};
    L l=li[i].l;
    if(n==m) return l;
    L s;
    if(k<=(n+m)/2) s=get(li[i].x,n,(n+m)/2,k);
    else s=get(li[i].y,(n+m)/2+1,m,k);
    if(l.sol(k)<s.sol(k)) return l;
    return s;
}
 
int f(ll v)
{
    li.clear();
    li.push_back({});
    L bf={0,0,0};
    li.push_back({0,0,{0,0,0}});
    int ff=0;
    for(int t=1;t<=a;t++)
    if(o[t]!=t||ck[t])
    {
        L l=get(1,1,100000,t);
        ff=l.n+1;
        z=l.sol(t)+(ll)t*t+v;
        
        //printf("%d %lld\n",t,z);
        bf={-2*o[t],z+(ll)o[t]*o[t],l.n+1};
        add(1,1,100000,{-2*o[t],z+(ll)o[t]*o[t],l.n+1});
    }
    else
    {
      bf.a-=2;
      bf.b++;
      add(1,1,100000,bf);
    }
    return ff;
}
 
ll take_photos(int n,int m,int k,vector<int> r,vector<int> c)
{
    b=n;
    a=m;
    for(int t=1;t<=a;t++) o[t]=t;
    for(int t=0;t<b;t++)
    {
      ck[max(r[t],c[t])+1]=1;
      o[max(r[t],c[t])]=min(min(r[t],c[t]),o[max(r[t],c[t])]);
    }
    for(int t=a-1;t;t--)
        o[t]=min(o[t],o[t+1]);
    ll s=0,e=100000000000;
    int x=0,y=a+1;
    for(;s<=e;)
    {
        ll h=(s+e)/2;
        int ff=f(h);
        if(ff==k)
        {
            //printf("@@%d %lld %lld %lld %lld\n",ff,z-k*h,h,s,e);
            return z-k*h;
        }
        if(ff>k)
        {
            if(x<ff) x=ff,lv=z-ff*h;
            s=h+1;
        }
        else
        {
            if(y>ff) y=ff,rv=z-ff*h;
            e=h-1;
        }
 
 
        //printf("%d %lld %lld %lld %lld %lld %lld %d %d\n",ff,z-k*h,h,s,e,lv,rv,x,y);
    }
    return rv+(lv-rv)/(y-x)*(y-min(k,y));
}

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