답안 #1057060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057060	2024-08-13T13:48:05 Z	underwaterkillerwhale	Fire (BOI24_fire)	C++17	48 / 100	85 ms	68016 KB

Main

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e6 + 7;
const int Mod = 1e9 + 7;
const int INF = 2e9 + 7;
const ll BASE = 137;
const int szBL = 320;

int m, n;
pii a[N];
int spt[N][25];
pii mx[N][25];

void solution () {
    cin >> n >> m;
    rep (i, 1, n) {
        cin >> a[i].fs >> a[i].se;
        if (a[i].se < a[i].fs) a[i].se = m + a[i].se;
    }
    sort (a + 1, a + 1 + n, [] (pii A, pii B) { return A.fs < B.fs || (A.fs == B.fs && A.se > B.se); });

    rep (i, 1, n) {
        mx[i][0] = MP(a[i].se, i);
    }
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
    auto get = [] (int L, int R) -> pii {
        assert (L <= R);
        int K = 31 - __builtin_clz(R - L + 1);
        return max(mx[L][K], mx[R - (1 << K) + 1][K]);
    };
    rep (i, 1, n) {
        if (a[i].se >= m) spt[i][0] = i;
        else {
            int lf = i, rt = n;
            while (lf < rt) {
                int mid = lf + rt + 1 >> 1;
                if (a[mid].fs <= a[i].se) lf = mid;
                else rt = mid - 1;
            }
            spt[i][0] = get(i, lf).se;
//            cout << i << " "<<spt[i][0] <<"\n";
        }
    }
    rep (j, 1, 20)
    rep (i, 1, n)
        spt[i][j] = spt[spt[i][j - 1]][j - 1];
    int ans = INF;
    rep (i, 1, n) {
        int toreach = m + a[i].fs;
        int cur = i, res = 0;
        reb (j, 20, 0) {
            if (a[spt[cur][j]].se < toreach) {
                cur = spt[cur][j];
                res += (1 << j);
            }
        }
        ++res;
        cur = spt[cur][0];
//        cout << i<<" "<<cur <<" "<<toreach<<"\n";
        if (a[cur].se >= toreach) ans = min(ans, res + 1);
    }
    if (ans == INF) cout << -1 <<"\n";
    else  cout << ans <<"\n";

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +2
2 + 8 * 2 - 9
6 2
1 5 2 3 1 1
1 2 3 3 2
4 5
6 6
*/

Compilation message

Main.cpp: In function 'void solution()':
Main.cpp:45:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   45 |             mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
      |                                                       ~~^~~
Main.cpp:56:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |                 int mid = lf + rt + 1 >> 1;
      |                           ~~~~~~~~^~~

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	0 ms	4444 KB	Output is correct
3	Correct	0 ms	4564 KB	Output is correct
4	Correct	0 ms	4444 KB	Output is correct
5	Correct	1 ms	4440 KB	Output is correct
6	Correct	0 ms	4444 KB	Output is correct
7	Correct	0 ms	4444 KB	Output is correct
8	Correct	0 ms	4444 KB	Output is correct
9	Correct	0 ms	4564 KB	Output is correct
10	Correct	0 ms	4444 KB	Output is correct
11	Correct	0 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	0 ms	4444 KB	Output is correct
14	Correct	0 ms	4444 KB	Output is correct
15	Correct	0 ms	4444 KB	Output is correct
16	Correct	0 ms	4444 KB	Output is correct
17	Correct	0 ms	4444 KB	Output is correct
18	Correct	0 ms	4560 KB	Output is correct
19	Correct	0 ms	4444 KB	Output is correct
20	Correct	0 ms	4444 KB	Output is correct
21	Correct	0 ms	4444 KB	Output is correct
22	Correct	0 ms	4444 KB	Output is correct
23	Correct	0 ms	4444 KB	Output is correct

Subtask #2
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	0 ms	4444 KB	Output is correct
3	Correct	0 ms	4564 KB	Output is correct
4	Correct	0 ms	4444 KB	Output is correct
5	Correct	1 ms	4440 KB	Output is correct
6	Correct	0 ms	4444 KB	Output is correct
7	Correct	0 ms	4444 KB	Output is correct
8	Correct	0 ms	4444 KB	Output is correct
9	Correct	0 ms	4564 KB	Output is correct
10	Correct	0 ms	4444 KB	Output is correct
11	Correct	0 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	0 ms	4444 KB	Output is correct
14	Correct	0 ms	4444 KB	Output is correct
15	Correct	0 ms	4444 KB	Output is correct
16	Correct	0 ms	4444 KB	Output is correct
17	Correct	0 ms	4444 KB	Output is correct
18	Correct	0 ms	4560 KB	Output is correct
19	Correct	0 ms	4444 KB	Output is correct
20	Correct	0 ms	4444 KB	Output is correct
21	Correct	0 ms	4444 KB	Output is correct
22	Correct	0 ms	4444 KB	Output is correct
23	Correct	0 ms	4444 KB	Output is correct
24	Correct	1 ms	4444 KB	Output is correct
25	Incorrect	1 ms	4444 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	0 ms	4444 KB	Output is correct
3	Correct	0 ms	4564 KB	Output is correct
4	Correct	0 ms	4444 KB	Output is correct
5	Correct	1 ms	4440 KB	Output is correct
6	Correct	0 ms	4444 KB	Output is correct
7	Correct	0 ms	4444 KB	Output is correct
8	Correct	0 ms	4444 KB	Output is correct
9	Correct	0 ms	4564 KB	Output is correct
10	Correct	0 ms	4444 KB	Output is correct
11	Correct	0 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	0 ms	4444 KB	Output is correct
14	Correct	0 ms	4444 KB	Output is correct
15	Correct	0 ms	4444 KB	Output is correct
16	Correct	0 ms	4444 KB	Output is correct
17	Correct	0 ms	4444 KB	Output is correct
18	Correct	0 ms	4560 KB	Output is correct
19	Correct	0 ms	4444 KB	Output is correct
20	Correct	0 ms	4444 KB	Output is correct
21	Correct	0 ms	4444 KB	Output is correct
22	Correct	0 ms	4444 KB	Output is correct
23	Correct	0 ms	4444 KB	Output is correct
24	Correct	1 ms	4444 KB	Output is correct
25	Incorrect	1 ms	4444 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #4
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4564 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	0 ms	4444 KB	Output is correct
5	Correct	0 ms	4444 KB	Output is correct
6	Correct	0 ms	4584 KB	Output is correct
7	Correct	1 ms	4440 KB	Output is correct
8	Correct	0 ms	4444 KB	Output is correct
9	Correct	0 ms	4444 KB	Output is correct
10	Correct	0 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	0 ms	4444 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	2 ms	6748 KB	Output is correct
16	Correct	2 ms	6748 KB	Output is correct
17	Correct	2 ms	6748 KB	Output is correct
18	Correct	2 ms	6892 KB	Output is correct
19	Correct	2 ms	6744 KB	Output is correct
20	Correct	51 ms	64852 KB	Output is correct
21	Correct	78 ms	67924 KB	Output is correct
22	Correct	76 ms	67920 KB	Output is correct
23	Correct	77 ms	67136 KB	Output is correct
24	Correct	71 ms	67900 KB	Output is correct
25	Correct	85 ms	67252 KB	Output is correct
26	Correct	70 ms	67924 KB	Output is correct
27	Correct	66 ms	68016 KB	Output is correct
28	Correct	71 ms	67912 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	0 ms	4444 KB	Output is correct
3	Correct	0 ms	4444 KB	Output is correct
4	Correct	0 ms	4444 KB	Output is correct
5	Correct	1 ms	4440 KB	Output is correct
6	Correct	0 ms	4444 KB	Output is correct
7	Correct	1 ms	4440 KB	Output is correct
8	Correct	1 ms	4440 KB	Output is correct
9	Correct	1 ms	4440 KB	Output is correct
10	Correct	0 ms	4444 KB	Output is correct
11	Correct	0 ms	4444 KB	Output is correct
12	Correct	2 ms	6748 KB	Output is correct
13	Correct	2 ms	6744 KB	Output is correct
14	Correct	2 ms	6748 KB	Output is correct
15	Correct	56 ms	64992 KB	Output is correct
16	Correct	62 ms	66900 KB	Output is correct
17	Correct	67 ms	67924 KB	Output is correct
18	Correct	69 ms	67920 KB	Output is correct
19	Correct	71 ms	67920 KB	Output is correct
20	Correct	63 ms	67008 KB	Output is correct

Subtask #6
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	0 ms	4444 KB	Output is correct
3	Correct	0 ms	4564 KB	Output is correct
4	Correct	0 ms	4444 KB	Output is correct
5	Correct	1 ms	4440 KB	Output is correct
6	Correct	0 ms	4444 KB	Output is correct
7	Correct	0 ms	4444 KB	Output is correct
8	Correct	0 ms	4444 KB	Output is correct
9	Correct	0 ms	4564 KB	Output is correct
10	Correct	0 ms	4444 KB	Output is correct
11	Correct	0 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	0 ms	4444 KB	Output is correct
14	Correct	0 ms	4444 KB	Output is correct
15	Correct	0 ms	4444 KB	Output is correct
16	Correct	0 ms	4444 KB	Output is correct
17	Correct	0 ms	4444 KB	Output is correct
18	Correct	0 ms	4560 KB	Output is correct
19	Correct	0 ms	4444 KB	Output is correct
20	Correct	0 ms	4444 KB	Output is correct
21	Correct	0 ms	4444 KB	Output is correct
22	Correct	0 ms	4444 KB	Output is correct
23	Correct	0 ms	4444 KB	Output is correct
24	Correct	1 ms	4444 KB	Output is correct
25	Incorrect	1 ms	4444 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

답안 #1057060

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 0 / 17.0

Subtask #3 0 / 9.0

Subtask #4 13.0 / 13.0

Subtask #5 21.0 / 21.0

Subtask #6 0 / 26.0

Subtask #1
14.0 / 14.0

Subtask #2
0 / 17.0

Subtask #3
0 / 9.0

Subtask #4
13.0 / 13.0

Subtask #5
21.0 / 21.0

Subtask #6
0 / 26.0