oj.uz

Submission #1057060

# Submission time Handle Problem Language Result Execution time Memory
1057060 2024-08-13T13:48:05 Z underwaterkillerwhale Fire (BOI24_fire) C++17
48 / 100
 85 ms 68016 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -