Submission #1184272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184272		segfault_ikuyo	Aliens (IOI16_aliens)	C++20	4 / 100	0 ms	328 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define l first
#define r second
#define pb push_back
using namespace std;

const int maxn=1e5+5;
int N;
ll dp[maxn],cnt[maxn];
pll res;

vector<pii> seg,seg2;

int cmp(pii a,pii b){
    if(a.l==b.l) return a.r>b.r;
    return a.l<b.l;
}


struct line{
    int a;
    ll b,c;
};

deque<line> dq;

ll gety(line a,int x){
    return a.b*x+a.c;
}

double getidx(line a, line b){
    if(b.b==a.b) return 1e18;
    return (double)(a.c-b.c)/(double)(b.b-a.b);
}

pll check(ll lmb){
    dq.clear();
    dq.push_back({0,-2*(seg[1].l-1ll),dp[0]+pow(seg[1].l-1ll,2)-pow(max(0ll,seg[0].r-(seg[1].l-1ll)),2)});
    for(int i=1;i<seg.size()-1;i++){
        while(dq.size()>1&&gety(dq.front(),seg[i].r)>gety(*(++dq.begin()),seg[i].r)) dq.pop_front();
        
        line u=dq.front();
        //dp[i]=dp[u.a]+lmb+pow((seg[i].r-(seg[u.a+1].l-1ll)),2)-pow(max(0ll,seg[u.a].r-(seg[u.a+1].l-1ll)),2);
        //dp[i]=dp[u.a]+lmb+pow(seg[i].r,2)-2*seg[i].r*(seg[u.a+1].l-1ll)+pow(seg[u.a+1].l-1ll,2)-pow(max(0ll,seg[u.a].r-(seg[u.a+1].l-1ll)),2);
        dp[i]=gety(u,seg[i].r)+pow(seg[i].r,2)+lmb;
        cnt[i]=cnt[u.a]+1;
        line nl={seg[i].r,-2*(seg[i+1].l-1ll),dp[i]+pow(seg[i+1].l-1ll,2)-pow(max(0ll,seg[i].r-(seg[i+1].l-1ll)),2)};

        while(dq.size()>1){
            line la=dq.back();
            line lb=*(--(--dq.end()));
            double idx=getidx(nl,la);
            if(gety(la,idx)<gety(lb,idx)) break;
            else dq.pop_back();
        }
        dq.push_back(nl);
        //cout<<dp[i]<<' '<<cnt[i]<<'\n';
    }
    return {dp[seg.size()-2],cnt[seg.size()-2]};
}

long long take_photos(int n,int m,int k,vector<int> r,vector<int> c){
    N=n;
    for(int i=0;i<n;i++) seg2.pb({min(r[i],c[i]),max(r[i],c[i])});
    sort(seg2.begin(),seg2.end(),cmp);
    seg.push_back({-1,-1});
    for(pii i:seg2) if(seg.back().r<i.r) seg.pb(i);
    seg.push_back({-1,-1});
    ll low=0;
    ll high=1e9;
    while(low<high){
        ll mid=low+(high-low)/2;
        res=check(mid);
        if(res.r<=k) high=mid;
        else low=mid+1;
        //cout << mid << ' ' << res.l << ' ' << res.r<<"-------------\n";
    }

    res=check(low);
    //cout << res.l << ' ' << res.r<<'\n';
    return res.l-low*k;
}

// 5 7 2 0 3 4 4 4 6 4 5 4 6
// 2 6 10 1 4 4 1

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, long long int> check(long long int)':
aliens.cpp:43:64: warning: narrowing conversion of '(((__gnu_cxx::__promote_2<long long int, int, double, double>::__type)dp[0] + std::pow<long long int, int>((((long long int)seg.std::vector<std::pair<int, int> >::operator[](1).std::pair<int, int>::first) - 1), 2)) - std::pow<long long int, int>(((long long int)std::max<long long int>(0, (((long long int)seg.std::vector<std::pair<int, int> >::operator[](0).std::pair<int, int>::second) - (((long long int)seg.std::vector<std::pair<int, int> >::operator[](1).std::pair<int, int>::first) - 1)))), 2))' from '__gnu_cxx::__promote_2<long long int, int, double, double>::__type' {aka 'double'} to 'long long int' [-Wnarrowing]
   43 |     dq.push_back({0,-2*(seg[1].l-1ll),dp[0]+pow(seg[1].l-1ll,2)-pow(max(0ll,seg[0].r-(seg[1].l-1ll)),2)});
      |                                       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:52:74: warning: narrowing conversion of '(((__gnu_cxx::__promote_2<long long int, int, double, double>::__type)dp[i] + std::pow<long long int, int>((((long long int)seg.std::vector<std::pair<int, int> >::operator[](((std::vector<std::pair<int, int> >::size_type)(i + 1))).std::pair<int, int>::first) - 1), 2)) - std::pow<long long int, int>(((long long int)std::max<long long int>(0, (((long long int)seg.std::vector<std::pair<int, int> >::operator[](((std::vector<std::pair<int, int> >::size_type)i)).std::pair<int, int>::second) - (((long long int)seg.std::vector<std::pair<int, int> >::operator[](((std::vector<std::pair<int, int> >::size_type)(i + 1))).std::pair<int, int>::first) - 1)))), 2))' from '__gnu_cxx::__promote_2<long long int, int, double, double>::__type' {aka 'double'} to 'long long int' [-Wnarrowing]
   52 |         line nl={seg[i].r,-2*(seg[i+1].l-1ll),dp[i]+pow(seg[i+1].l-1ll,2)-pow(max(0ll,seg[i].r-(seg[i+1].l-1ll)),2)};
      |                                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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