제출 #1175502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175502		Haanhtien	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	635 ms	93724 KiB

Main

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

#define ll long long
#define FOR(i, a, b) for(int i=(a), _b=(b); i<=_b; i++)
#define FORD(i, a, b) for(int i=(a), _b=(b); i>=_b; i--)
#define BIT(i, j) ((i>>j)&1)
#define pb push_back
#define ii pair<ll, ll>
#define pii pair<ll, ii>
#define all(x) x.begin(), x.end()
#define fi first
#define se second

const ll inf = 1e18;
const ll mod = 1e9+7;
const ll N = 100005;
const ll M = 50005;

int n, m, k, q, L[20][N], R[20][N];
ii st[20][4 * N];

ii getP(ii a, ii b)
{
    return {min(a.fi, b.fi), max(a.se, b.se)};
}
void build (int type, int id = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        st[type][id] = {L[type][l], R[type][l]};
        return;
    }
    int mid = l + r >> 1;
    build (type, id << 1, l, mid);
    build (type, id << 1 | 1, mid + 1, r);

    st[type][id] = getP(st[type][id << 1], st[type][id << 1 | 1]);
}

ii get (int type, int u, int v, int id = 1, int l = 1, int r = n)
{
    if (v < l || u > r) return {n + 1, 0};
    if (u <= l && r <= v) return st[type][id];
    int mid = l + r >> 1;
    ii x = get (type, u, v, id << 1, l, mid);
    ii y = get (type, u, v, id << 1 | 1, mid + 1, r);
    return getP(x, y);
}
void solve()
{
    cin >> n >> k >> m;

    for (int i = 0; i <= 18; i++)
        for (int j = 1; j <= n; j++)
            L[i][j] = R[i][j] = j;

    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        L[0][a] = min(L[0][a], b);
        R[0][a] = max(R[0][a], b);
    }
    
    build (0);

    for (int i = 1; i <= n; i++)
    {
        auto [u, v] = get (0, max(1, i - k + 1), i);
        R[0][i] = v;
        auto [x, y] = get (0, i, min(n, i + k - 1));
        L[0][i] = x;
        //.cout << L[0][i] << ' ' << R[0][i] << '\n';
    }

    build(0);

    for (int i = 1; i <= 18; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            auto [u, v] = get (i - 1, L[i - 1][j], R[i - 1][j]);
            L[i][j] = u;
            R[i][j] = v;
        }
        build (i);
    }
    
    cin >> q;
    while (q--)
    {
        int s, t;
        cin >> s >> t;
        ll ans = 0;
        int l = s, r = s;
        for (int i = 18; i >= 0; i--)
        {
            auto [u, v] = get(i, l, r);
            if (t < u || t > v)
            {
                l = u, r = v;
                ans += (1 << i);
            }
        }

        auto [u, v] = get (0, l, r);
        if (u <= t && v >= t)
        {
            cout << ans + 1 << '\n';
        }
        else cout << -1 << '\n';
    }

    

}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "task"
    if(fopen(task".inp", "r"))
    {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    if(fopen("task.inp", "r"))
    {
        freopen("task.INP", "r", stdin);
        freopen("task.OUT", "w", stdout);
    }

    solve();
    return 0;
}

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

Main.cpp: In function 'int main()':
Main.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("task.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen("task.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13