oj.uz

Submission #801756

# Submission time Handle Problem Language Result Execution time Memory
801756 2023-08-02T07:29:39 Z 이동현(#10092) Cultivation (JOI17_cultivation) C++17
0 / 100
 34 ms 468 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int r, c, n;
    cin >> r >> c >> n;
    assert(n <= 100);
    vector<array<int, 2>> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i][0] >> a[i][1];
        --a[i][0];
        --a[i][1];
    }

    vector<int> dpu;
    sort(a.begin(), a.end());
    for(int i = 0; i < n; ++i){
        dpu.push_back(r - a[i][0]);
        dpu.push_back(r - a[i][0] - 1);
        for(int j = i + 1; j < n; ++j){
            dpu.push_back(a[j][0] - a[i][0]);
            dpu.push_back(a[j][0] - a[i][0] + 1);
        }
        for(int j = 0; j < n; ++j){
            dpu.push_back(a[j][0] + r - a[i][0]);
            dpu.push_back(a[j][0] + r - a[i][0] - 1);
        }
    }

    sort(dpu.begin(), dpu.end());
    dpu.erase(unique(dpu.begin(), dpu.end()), dpu.end());

    auto sol = [&](int dulen)->int{
        int rv = (int)1e18;

        vector<array<int, 3>> que;
        vector<vector<array<int, 3>>> mx(3);
        
        for(int j = 0; j < n; ++j){
            que.push_back({a[j][0], -1, a[j][1]});
            que.push_back({a[j][0] + dulen, 1, a[j][1]});
        }

        sort(que.begin(), que.end());

        multiset<int> st;

        for(int j = 0; j < (int)que.size(); ++j){
            auto i = que[j];
            if(!(int)st.size()){
                mx[0].push_back({i[0] - r + 1, -1, (int)1e18});
                mx[0].push_back({i[0], 1, (int)1e18});
            }
            if(i[1] == -1){
                st.insert(i[2]);
            }
            else{
                st.erase(st.find(i[2]));
            }

            if((j == (int)que.size() - 1 || que[j + 1][0] > i[0])){
                if(!(int)st.size()){
                    mx[0].push_back({i[0] - r + 1, -1, (int)1e18});
                    mx[0].push_back({i[0] + 1, 1, (int)1e18});
                }
                else{
                    mx[1].push_back({i[0] - r + 1, -1, *st.begin()});
                    mx[1].push_back({i[0] + 1, 1, *st.begin()});
                    mx[2].push_back({i[0] - r + 1, -1, c - *(--st.end()) - 1});
                    mx[2].push_back({i[0] + 1, 1, c - *(--st.end()) - 1});

                    for(int x = j; x >= 0 && que[x][0] == que[j][0]; --x){
                        int lst = (int)1e18;
                        auto p2 = st.lower_bound(que[x][2]);
                        if(p2 != st.begin() && p2 != st.end()){
                            auto p1 = p2;
                            --p1;
                            mx[0].push_back({i[0] - r + 1, -1, *p2 - *p1});
                            mx[0].push_back({i[0] + 1, 1, *p2 - *p1});
                        }
                    }
                }
            }
        }

        for(int i = 0; i < 3; ++i) sort(mx[i].begin(), mx[i].end());
        vector<multiset<int>> mxst(3);
        vector<int> pos(3);
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < 3; ++j){
                while(pos[j] < (int)mx[j].size() && mx[j][pos[j]][0] <= a[i][0]){
                    if(mx[j][pos[j]][1] == -1) mxst[j].insert(mx[j][pos[j]][2]);
                    else mxst[j].erase(mxst[j].find(mx[j][pos[j]][2]));
                    ++pos[j];
                }

                assert((int)mxst[j].size());
            }

            rv = min(rv, max(*(--mxst[0].end()) - 1, *(--mxst[1].end()) + *(--mxst[2].end())));
        }

        return rv;
    };

    int ans = (int)1e18;

    for(auto&dulen:dpu){
        if(dulen > 0) ans = min(ans, dulen - 1 + sol(dulen));
    }

    cout << ans << '\n';
    
    return 0;
}

Compilation message

cultivation.cpp: In lambda function:
cultivation.cpp:80:29: warning: unused variable 'lst' [-Wunused-variable]
   80 |                         int lst = (int)1e18;
      |                             ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 352 KB Output is correct
2 Incorrect 34 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 352 KB Output is correct
2 Incorrect 34 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -