제출 #1239297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239297		Zbyszek99	Shortcut (IOI16_shortcut)	C++20	0 / 100	0 ms	328 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

ll P[1000001];
ll D[1000001];
ll C;
int n;
vector<pll> vsort1;
vector<pll> vsort2;

bool check(ll K)
{
    ll left_plus = -1e18;
    ll right_plus = 1e18;
    ll left_minus = -1e18;
    ll right_minus = 1e18;
    // plus
    ll cur_max_sum = -1e18;
    ll cur_min_dif = 1e18;
    ll cur_max_dif = -1e18;
    ll cur_min_sum = 1e18;
    int cur_vsort2 = 0;
    forall(it,vsort1)
    {
        while(cur_vsort2 < siz(vsort2) && vsort2[cur_vsort2].ff + it.ff > K)
        {
            int v = vsort2[cur_vsort2].ss;
            cur_vsort2++;
            cur_max_sum = max(cur_max_sum,P[v]+D[v]);
            cur_min_dif = min(cur_min_dif,P[v]-D[v]);
            cur_max_dif = max(cur_max_dif,-P[v]+D[v]);
            cur_min_sum = min(cur_min_sum,-P[v]-D[v]);
        }
        int v = it.ss;
        left_plus = max(left_plus,cur_max_sum+P[v]+D[v]+C-K);
        right_plus = min(right_plus,cur_min_dif+P[v]-D[v]-C+K);
        left_minus = max(left_minus,cur_max_dif+P[v]+D[v]+C-K);
        right_minus = min(right_minus,cur_min_sum+P[v]-D[v]-C+K);
    }
    rep(i,n)
    {
        rep2(j,i+1,n)
        {
            ll sum = P[i]+P[j];
            ll dif = P[j]-P[i];
            if(sum >= left_plus && sum <= right_plus && dif >= left_minus && dif <= right_minus) return 1;
        }
    }
    return 0;
}

ll find_shortcut(int N, vi L, vi d, int c)
{
    n = N;
    C = c;
    ll sum = 0;
    vl Ds;
    rep(i,n)
    {
        Ds.pb(d[i]);
        D[i] = d[i];
        P[i] = sum;
        sum += L[i];
        vsort1.pb({P[i]+D[i],i});
        vsort2.pb({-P[i]+D[i],i});
    }
    sort(all(vsort1));
    sort(all(vsort2));
    reverse(all(vsort2));
    sort(all(Ds));
    reverse(all(Ds));
    ll l = Ds[0]+Ds[1];
    ll r = 1e9*(ll)n;
    ll ans = 0;
    while(l <= r)
    {
        ll mid = (l+r)/2;
        if(check(mid))
        {
            ans = mid;
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    return ans;
}

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

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3