제출 #1038578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038578		vjudge1	Global Warming (CEOI18_glo)	C++17	45 / 100	2080 ms	22352 KiB

glo

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1e6 + 3;
const ll inf = 1e18;
const ll oo = 1e9;

ll n, x;
ll a[maxn + 3], l[maxn + 3], r[maxn + 3], d1[maxn + 3], d2[maxn + 3], m, ans, temp1[maxn + 3], temp2[maxn + 3];

int BinSearch1(int v, ll d[])
{
    int l = 1, h = m, mid;
    while (l <= h)
    {
        mid = (l + h)/2;
        if (a[d[mid]] < v)l = mid + 1;
        else h = mid - 1;
    }
    return h;
}

int BinSearch2(int v, ll d[])
{
    int l = 1, h = m, mid;
    while (l <= h)
    {
        mid = (l + h)/2;
        if (a[d[mid]] > v)l = mid + 1;
        else h = mid - 1;
    }
    return h;
}

int main()
{
  //  freopen("INP.inp", "r", stdin);
  //  freopen("INP.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int res = 1;
    cin >> n >> x;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    fill_n(l, maxn, 1);
    fill_n(r, maxn, 1);
    for(int i = 1; i <= n; i++)
    {
        int k = BinSearch1(a[i], d1);
        d1[k + 1] = i;
        l[i] = k + 1;
        if (m < l[i])
        {
            m = l[i];
        }
        temp1[i] = m;
    }
    m = 0;
    for(int i = n; i >= 1; i--)
    {
        int k = BinSearch2(a[i], d2);
        d2[k + 1] = i;
        r[i] = k + 1;
        if(m < r[i])
        {
            m = r[i];
        }
        temp2[i] = m;
    }
    /*for(int i = 1; i <= n; i++)
    {
        cout << l[i] << ' ' << r[i] << '\n';
    }*/
    if(x == oo)
    {
        for(int i = 1; i <= n; i++)
        {
            ans = max(ans, temp1[i] + temp2[i + 1]);
        }
        cout << ans;
        return 0;
    }
    for(int i = 1; i < n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            if(a[i] + 1 - a[j] <= x)
            {
                ans = max(ans, l[i] + r[j]);
                //cout << i << ' ' << j << ' ' << ans << '\n';
            }
        }
    }
    cout << ans;
}

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

glo.cpp: In function 'int main()':
glo.cpp:42:9: warning: unused variable 'res' [-Wunused-variable]
   42 |     int res = 1;
      |         ^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25