제출 #1183368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183368		dnnnda	Aliens (IOI16_aliens)	C++20	100 / 100	126 ms	6996 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
#define init(arr,val) memset(arr,val,sizeof(arr))
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

struct Line{
    ll m, k, t;
    Line(){};
    Line(ll m, ll k, ll t): m(m), k(k), t(t){};
    ll operator()(const ll &x) const{
        return 1LL*m*x+k;
    }
};

ll l[100005], r[100005]={-1}, n, cov[100005], cnt;
deque<Line> dq;

bool over(Line L1, Line L2, ll val){
    return L1(val)>L2(val)||L1(val)==L2(val)&&abs(L1.t)<abs(L2.t);
}

bool del(Line L1, Line L2, Line L){
    return  (L.k-L2.k)*(L1.m-L2.m)<(L2.k-L1.k)*(L2.m-L.m) ||
            (L.k-L2.k)*(L1.m-L2.m)==(L2.k-L1.k)*(L2.m-L.m) && (abs(L1.t)>abs(L2.t)||abs(L.t)>abs(L2.t));
}

pair<ll,ll> solve(ll p){ // fee, -max_trans_time
    dq.clear();
    dq.push_back(Line(-2*l[1],l[1]*l[1]-2*l[1]-cov[0]*cov[0],0));

    for(int i=1 ; i<=n ; i++){
        while(dq.size()>=2&&over(dq[0],dq[1],r[i])) dq.pop_front();
        pair<ll,ll> temp={inff,0};
        temp=min(temp,{dq[0](r[i])+(r[i]+1)*(r[i]+1)+p,dq[0].t-1});

        if(i==n) return {temp.F,-temp.S};
        else{
            Line line(-2*l[i+1],temp.F+l[i+1]*l[i+1]-2*l[i+1]-cov[i]*cov[i],temp.S);
            while(dq.size()>=2&&del(dq.end()[-2],dq.end()[-1],line)) dq.pop_back();
            dq.push_back(line);
        }
    }
}

ll take_photos(int N, int M, int K, vector<int> _r, vector<int> _c){
    vector<pair<int,int>> v, v2;
    for(int i=0 ; i<N ; i++){
        if(_r[i]>_c[i]) swap(_r[i],_c[i]);
        v.push_back({_r[i],_c[i]});
    }
    sort(v.begin(),v.end());
    for(int i=0 ; i<N ; i++){
        if(v2.empty()||v[i].S>v2.back().S&&v[i].F>v2.back().F) v2.push_back(v[i]);
        else if(v[i].F==v2.back().F) v2.back().S=v[i].S;
    }
    n=v2.size();

    for(int i=0 ; i<n ; i++) l[i+1]=v2[i].F, r[i+1]=v2[i].S;
    for(int i=0 ; i<n ; i++) cov[i]=max(0LL,r[i]-l[i+1]+1);

    if(K==1) return (r[n]-l[1]+1)*(r[n]-l[1]+1);
    ll p=0;
    auto ans1=solve(0);
    if(ans1.S<=K) return ans1.F;
    for(ll jump=1'000'000'000'000 ; jump ; jump>>=1){
        while(solve(p+jump).S>=K) p+=jump;
    }
    auto temp=solve(p);
    return temp.F-p*K;
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'std::pair<long long int, long long int> solve(long long int)':
aliens.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^
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: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40