oj.uz

Submission #1067480

# Submission time Handle Problem Language Result Execution time Memory
1067480 2024-08-20T17:44:30 Z Essa2006 Fire (BOI24_fire) C++14
0 / 100
 335 ms 98900 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 << 15;
array<int, 2> bad = {(int)1e5 + 1, (int)1e5 + 1};
vector<array<int, 2>> S(2e5 + 1, bad);

void clear_them() {
    S.clear();
    S.resize(2e5 + 1, bad);
}

void update(int i, int idx, int val) {
    S[idx][i] = val;
}

int get(int i, int id, int u, int v, int l, int r) {
    int mn = 1e5 + 1;
    for (int j = u; j <= v; j++) {
        mn = min(mn, S[j][i]);
    }   
    return mn;
}



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++) {
        int cur = 0;
        vector<vector<int>> Events(sz);
        for (int j = 0; j < n; j++) {
            Events[A[j][0]].push_back(j);
            Events[A[j][1]].push_back(j);
        }
        
        vector<int> Prf(sz + 1, n + 1), Suf(sz + 1, n + 1);
        
        Prf[cur] = 0;
        update(0, cur, Prf[cur]);
        for (int i = cur + 1; i % sz != cur; i++) {
            i %= sz;
            for (auto j : Events[i]) {
                if (A[j][0] < A[j][1]) {
                    if (i != A[j][1] || (cur > A[j][0] && cur < A[j][1])) {
                        continue;
                    }
                    
                    Prf[i] = min(Prf[i], get(0, 1, A[j][0], A[j][1], 0, N - 1) + 1);
                }
                else {
                    if (i != A[j][1] || cur > A[j][0] || cur < A[j][1]) {
                        continue;
                    }
                    
                    Prf[i] = min(Prf[i], min(get(0, 1, A[j][0], sz - 1, 0, N - 1), get(0, 1, 0, A[j][1], 0, N - 1)) + 1);
                }
            }
            
            update(0, i, Prf[i]);
        }
        
        Suf[cur] = 0;
        update(1, cur, Suf[cur]);
        for (int i = cur - 1; (i + sz) % sz != cur; i--) {
            i += sz;
            i %= sz;
            for (auto j : Events[i]) {
                if (A[j][0] < A[j][1]) {
                    if (i != A[j][0] || (cur > A[j][0] && cur < A[j][1])) {
                        continue;
                    }
                    
                    Suf[i] = min(Suf[i], get(1, 1, A[j][0], A[j][1], 0, N - 1) + 1);
                }
                else {
                    if (i != A[j][0] || cur > A[j][0] || cur < A[j][1]) {
                        continue;
                    }
                    
                    Suf[i] = min(Suf[i], min(get(1, 1, A[j][0], sz - 1, 0, N - 1), get(1, 1, 0, A[j][1], 0, N - 1)) + 1);
                }
            }
            
            update(1, i, Suf[i]);
        }
        
        clear_them();
        
        
        for (int i = cur - 2; (i + sz) % sz != cur; i--) {
            i += sz;
            i %= sz;
            
            Prf[i] = min(Prf[i], Prf[(i + 1) % sz]);
        }
        for (int i = cur + 2; i % sz != cur; i++) {
            i %= sz;
            
            Suf[i] = min(Suf[i], Suf[(i - 1 + sz) % sz]);
        }
        
        for (int i = 0; i < sz; i++) {
            if (i == cur) {
                continue;
            }

            ans = min(ans, Prf[i] + Suf[i]);
        }
        
        for (int i = 0; i < n; i++) {
            if (A[i][0] == cur) {
                ans = min(ans, Suf[A[i][1]] + 1);
            }
            else if (A[i][1] == cur) {
                ans = min(ans, Prf[A[i][0]] + 1);
            }
        }
    }
    
    
    if (ans == n + 1) {
        ans = -1;
    }
    
    cout << ans;
}

Compilation message

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1952 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 1 ms 1880 KB Output is correct
12 Correct 1 ms 1884 KB Output is correct
13 Correct 1 ms 1880 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 5 ms 3092 KB Output is correct
16 Correct 4 ms 2396 KB Output is correct
17 Correct 8 ms 2560 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Correct 5 ms 3164 KB Output is correct
20 Correct 28 ms 6872 KB Output is correct
21 Runtime error 335 ms 98900 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1880 KB Output is correct
8 Incorrect 1 ms 1880 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -