oj.uz

Submission #1068879

# Submission time Handle Problem Language Result Execution time Memory
1068879 2024-08-21T12:44:39 Z Essa2006 Fire (BOI24_fire) C++14
0 / 100
 700 ms 82516 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)

const int N = 1 << 18;
array<int, 2> bad = {(int)2e5, (int)2e5};
vector<array<int, 2>> S;

void clear_them() {
    S.clear();
    S.resize(2 * N, bad);
}

void update(int j, int id, int val) {
    id += N;
    S[id][j] = val;
    while (id /= 2) {
        S[id] = min(S[id * 2], S[id * 2 + 1]);
    }
}

int get(int j, int id, int u, int v, int l, int r) {
    if (l > v || r < u) {
        return 2e5;
    }
    
    if (l >= u && r <= v) {
        return S[id][j];
    }
    
    int md = (l + r) / 2;
    return min(get(j, id * 2, u, v, l, md), get(j, id * 2 + 1, u, v, md + 1, r));
}   

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> All;
    All.reserve(2 * n);
    
    vector<array<int, 2>> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i][0] >> A[i][1];
        
        All.push_back(A[i][0]);
        All.push_back(A[i][1]);
    }
    
    sort(all(All));
    map<int, int> new_;
    int cnt = 0;
    for (int i = 0; i < All.size(); i++) {
        if (!i || All[i] != All[i - 1]) {
            new_[All[i]] = cnt++;
        }
    }
    int sz = cnt;
    
    for (int i = 0; i < n; i++) {
        A[i][0] = new_[A[i][0]], A[i][1] = new_[A[i][1]];
    }
    
    int ans = n + 1;
    for (int k = 0; k < 1; k++) {
        if (k && All[k] == All[k - 1]) {
            continue;
        }
        
        clear_them();
        int cur = 0;
        vector<array<int, 2>> B = A;
        
        vector<vector<int>> Events(sz + 1);
        for (int i = 0; i < n; i++) {
            if (A[i][0] >= cur) {
                A[i][0] -= cur;
            }   
            else {
                A[i][0] += sz - cur;
            }
            if (A[i][1] >= cur) {
                A[i][1] -= cur;
            }   
            else {
                A[i][1] += sz - cur;
            }
            
            if (A[i][0] > A[i][1]) {
                A[i][1] = sz;
            }
            
            Events[A[i][0]].push_back(i);
            Events[A[i][1]].push_back(i);
        }
        
        
        vector<int> Prf(sz + 1, n + 1), Suf(sz + 1, n + 1);
        
        Prf[0] = 0;
        update(0, 0, Prf[0]);
        for (int i = 1; i <= sz; i++) {
            for (auto j : Events[i]) {
                if (i != A[j][1]) {
                    continue;
                }
                
                Prf[i] = min(Prf[i], get(0, 1, A[j][0], A[j][1] - 1, 0, N - 1) + 1);
            }
            update(0, i, Prf[i]);
        }
        
        Suf[sz] = 0;
        update(1, sz, Suf[sz]);
        for (int i = sz; i >= 0; i--) {
            for (auto j : Events[i]) {
                if (i != A[j][0]) {
                    continue;
                }
                
                for (int f = A[j][0] + 1; f <= A[j][1]; f++) {
                    Suf[i] = min(Suf[i], Suf[f] + 1);
                }
                
                Suf[i] = min(Suf[i], get(1, 1, A[j][0] + 1, A[j][1], 0, N - 1) + 1);
            }
            update(1, i, Suf[i]);
        }
        
        for (int i = 1; i <= sz; i++) {
            Suf[i] = min(Suf[i], Suf[i - 1]);
        }
        for (int i = sz - 1; i >= 0; i--) {
            Prf[i] = min(Prf[i], Prf[i + 1]);
        }
        
        for (int i = 0; i <= sz; i++) {
            ans = min(ans, Prf[i] + Suf[i]);
        }
        
        A = B;
    }
    if (ans == n + 1) { 
        ans = -1;
    }
    cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < All.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 3 ms 4440 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 4 ms 4608 KB Output is correct
10 Correct 3 ms 4440 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 3 ms 4388 KB Output is correct
13 Correct 3 ms 4444 KB Output is correct
14 Correct 4 ms 4440 KB Output is correct
15 Correct 12 ms 5724 KB Output is correct
16 Correct 6 ms 5212 KB Output is correct
17 Correct 14 ms 5000 KB Output is correct
18 Correct 6 ms 5208 KB Output is correct
19 Correct 12 ms 5724 KB Output is correct
20 Correct 72 ms 12096 KB Output is correct
21 Runtime error 700 ms 81984 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4440 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 4 ms 4440 KB Output is correct
8 Correct 3 ms 4696 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 4 ms 4696 KB Output is correct
12 Correct 9 ms 5836 KB Output is correct
13 Correct 9 ms 5304 KB Output is correct
14 Correct 7 ms 5212 KB Output is correct
15 Correct 66 ms 12092 KB Output is correct
16 Correct 431 ms 33876 KB Output is correct
17 Runtime error 657 ms 82516 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -