제출 #827727

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

Main

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

// 123

const int MAXN = 1e5;
int updL[18][MAXN], updR[18][MAXN];
int L[18][MAXN], R[18][MAXN];
int rmqL[18][MAXN], rmqR[18][MAXN];
int ansL[18][18][MAXN], ansR[18][18][MAXN];

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        int n, k, m;
        cin >> n >> k >> m;
        memset(updL, 0x3f, sizeof updL);
        memset(updR, 0xc3, sizeof updR);
        for (int i = 0; i < m; i++) {
                int a, b;
                cin >> a >> b;
                a--, b--;
                if (a < b) {
                        int c = min(a + k - 1, b - 1);
                        int j = __lg(c - a + 1);
                        c -= (1 << j) - 1;
                        updR[j][a] = max(updR[j][a], b);
                        updR[j][c] = max(updR[j][c], b);
                } else {
                        int c = max(a - k + 1, b + 1);
                        int j = __lg(a - c + 1);
                        a -= (1 << j) - 1;
                        updL[j][a] = min(updL[j][a], b);
                        updL[j][c] = min(updL[j][c], b);
                }
        }
        for (int i = 17; i > 0; i--) {
                for (int j = 0; j + (1 << i) <= n; j++) {
                        updL[i - 1][j] = min(updL[i - 1][j], updL[i][j]);
                        updL[i - 1][j + (1 << (i - 1))] = min(updL[i - 1][j + (1 << (i - 1))], updL[i][j]);
                        updR[i - 1][j] = max(updR[i - 1][j], updR[i][j]);
                        updR[i - 1][j + (1 << (i - 1))] = max(updR[i - 1][j + (1 << (i - 1))], updR[i][j]);
                }
        }
        memset(L, -1, sizeof L);
        memset(R, -1, sizeof R);
        for (int i = 0; i < n; i++) {
                L[0][i] = min(i, updL[0][i]);
                R[0][i] = max(i, updR[0][i]);
        }
        for (int i = 1; i < 18; i++) {
                for (int j = 0; j < n; j++) rmqL[0][j] = L[i - 1][j];
                for (int j = 0; j < n; j++) rmqR[0][j] = R[i - 1][j];
                for (int j = 1; j < 18; j++) {
                        for (int k = 0; k + (1 << j) <= n; k++) {
                                rmqL[j][k] = min(rmqL[j - 1][k], rmqL[j - 1][k + (1 << (j - 1))]);
                                rmqR[j][k] = max(rmqR[j - 1][k], rmqR[j - 1][k + (1 << (j - 1))]);
                        }
                }
                for (int j = 0; j < n; j++) {
                        int l = L[i - 1][j];
                        int r = R[i - 1][j];
                        int k = __lg(r - l + 1);
                        r -= (1 << k) - 1;
                        L[i][j] = min(rmqL[k][l], rmqL[k][r]);
                        R[i][j] = max(rmqR[k][l], rmqR[k][r]);
                }
        }
        memset(ansL, -1, sizeof ansL);
        memset(ansR, -1, sizeof ansR);
        for (int i = 0; i < 18; i++) {
                for (int j = 0; j <= n; j++) ansL[i][0][j] = L[i][j];
                for (int j = 0; j <= n; j++) ansR[i][0][j] = R[i][j];
                for (int j = 1; j < 18; j++) {
                        for (int k = 0; k + (1 << j) <= n; k++) {
                                ansL[i][j][k] = min(ansL[i][j - 1][k], ansL[i][j - 1][k + (1 << (j - 1))]);
                                ansR[i][j][k] = max(ansR[i][j - 1][k], ansR[i][j - 1][k + (1 << (j - 1))]);
                        }
                }
        }
        int q;
        cin >> q;
        while (q--) {
                int u, v;
                cin >> u >> v;
                u--, v--;
                int l = u, r = u;
                int res = 0;
                for (int i = 17; i >= 0; i--) {
                        int j = __lg(r - l + 1);
                        int rr = r - (1 << j) + 1;
                        int nl = min(ansL[i][j][l], ansL[i][j][rr]);
                        int nr = max(ansR[i][j][l], ansR[i][j][rr]);
                        if (nl != -1 && nr != -1 && nl > v || nr < v) l = nl, r = nr, res += (1 << i);
                }
                res++;
                cout << (res == (1 << 18) ? -1 : res) << '\n';
        }
}

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

Main.cpp: In function 'int32_t main()':
Main.cpp:95:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   95 |                         if (nl != -1 && nr != -1 && nl > v || nr < v) l = nl, r = nr, res += (1 << i);
      |                             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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