제출 #1067488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067488		Essa2006	Fire (BOI24_fire)	C++14	0 / 100	2081 ms	1648 KiB

Main

#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(1e4 + 1, bad);

void clear_them() {
    S.clear();
    S.resize(1e4 + 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 < All.size(); k++) {
        int cur = new_[All[k]];
        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]);
        }
        {
            int i = cur;
            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[sz] = min(Prf[sz], get(0, 1, A[j][0], A[j][1] - 1, 0, N - 1) + 1);
                }
                else {
                    if (i != A[j][1] || cur > A[j][0] || cur < A[j][1]) {
                        continue;
                    }

                    Prf[sz] = min(Prf[sz], min(get(0, 1, A[j][0], sz - 1, 0, N - 1), get(0, 1, 0, A[j][1] - 1, 0, N - 1)) + 1);
                }
            }
        }

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

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

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++) {
      |                     ~~^~~~~~~~~~~~
Main.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int k = 0; k < All.size(); k++) {
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26