oj.uz

Submission #925084

# Submission time Handle Problem Language Result Execution time Memory
925084 2024-02-10T18:15:18 Z ksujay2 Road Construction (JOI21_road_construction) C++17
6 / 100
 2041 ms 1008188 KB 
#include <bits/stdc++.h>
using namespace std;
const int BSZ = 500;
struct DS {
    int n;
    vector<int> x, y;
    vector<vector<int>> blocks;
    DS(vector<pair<int, int>>& p) {
        n = p.size();
        x.resize(n), y.resize(n);
        for(int i = 0; i < n; i++) x[i] = p[i].first, y[i] = p[i].second;
        blocks.resize((n - 1) / BSZ + 1, vector<int>(n, n));
        for(int i = 0; i < n; i++) {
            blocks[i / BSZ][x[i]] = min(blocks[i / BSZ][x[i]], y[i]); 
        }
        for(int i = 0; i < blocks.size(); i++) {
            for(int j = 1; j < n; j++) {
                blocks[i][j] = min(blocks[i][j], blocks[i][j - 1]);
            }
        }
    }

    int find_prev(int i, int lx, int ly) {
        while(i--) {
            if(i % BSZ == BSZ - 1) {
                if(blocks[i / BSZ][lx] > ly) {
                    i -= BSZ - 1;
                    continue;
                }
            }
            if(x[i] <= lx && y[i] <= ly) return i;
        }
        return i;
    }
};

int main() {
    int N, K; cin >> N >> K;
    vector<pair<int, int>> p(N);
    for(int i = 0; i < N; i++) cin >> p[i].first >> p[i].second;
    vector<int> sx(N), sy(N);
    for(int i = 0; i < N; i++) sx[i] = sy[i] = i;
    sort(sx.begin(), sx.end(), [&] (int a, int b) { return p[a].first == p[b].first ? p[a].second < p[b].second : p[a].first < p[b].first; });
    sort(sy.begin(), sy.end(), [&] (int a, int b) { return p[a].second == p[b].second ? p[a].first < p[b].first : p[a].second < p[b].second; });
    vector<int> cx(N), cy(N);
    for(int i = 0; i < N; i++) cx[sx[i]] = cy[sy[i]] = i;
    vector<int> o1(N), o2(N);
    for(int i = 0; i < N; i++) o1[i] = o2[i] = i;
    sort(o1.begin(), o1.end(), [&] (int a, int b) { return p[a].first + p[a].second < p[b].first + p[b].second; });
    sort(o2.begin(), o2.end(), [&] (int a, int b) { return p[a].first - p[a].second < p[b].first - p[b].second; });
    vector<pair<int, int>> c1(N), c2(N);
    for(int i = 0; i < N; i++) c1[i] = {cx[o1[i]], cy[o1[i]]}, c2[i] = {cx[o1[i]], N - 1 - cy[o1[i]]};
    DS ds1(c1), ds2(c2);
    priority_queue<pair<int, pair<int, int>>> pq1;
    priority_queue<pair<int, pair<int, int>>> pq2;
    auto diff1 = [&] (int i, int j) {
        return (p[o1[i]].first + p[o1[i]].second) - (p[o1[j]].first + p[o1[j]].second);
    };
    auto diff2 = [&] (int i, int j) {
        return (p[o2[i]].first - p[o2[i]].second) - (p[o2[j]].first - p[o2[j]].second);
    };
    for(int i = 0; i < N; i++) {
        int n1 = ds1.find_prev(i, c1[i].first, c1[i].second);
        int n2 = ds2.find_prev(i, c2[i].first, c2[i].second);
        if(n1 != -1)
            pq1.push({-diff1(i, n1), {i, n1}});
        if(n2 != -1)
            pq2.push({-diff2(i, n2), {i, n2}});
    }
    while(K--) {
        if(pq2.size() == 0 || pq1.top().first > pq2.top().first) {
            auto [v, ij] = pq1.top();
            cout << -v << endl;
            pq1.pop();
            int n1 = ds1.find_prev(ij.second, c1[ij.first].first, c1[ij.first].second);
            if(n1 != -1)
                pq1.push({-diff1(ij.first, n1), {ij.first, n1}});
        } else {
            auto [v, ij] = pq2.top();
            cout << -v << endl;
            pq2.pop();
            int n2 = ds2.find_prev(ij.second, c2[ij.first].first, c2[ij.first].second);
            if(n2 != -1)
                pq2.push({-diff2(ij.first, n2), {ij.first, n2}});
        }
    }
}

Compilation message

road_construction.cpp: In constructor 'DS::DS(std::vector<std::pair<int, int> >&)':
road_construction.cpp:16:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(int i = 0; i < blocks.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 1005308 KB Output is correct
2 Correct 1917 ms 1005176 KB Output is correct
3 Correct 311 ms 2872 KB Output is correct
4 Correct 1894 ms 1005060 KB Output is correct
5 Correct 1877 ms 1004980 KB Output is correct
6 Correct 1928 ms 1005292 KB Output is correct
7 Correct 1858 ms 1004648 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 27.0

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

Subtask #6
0 / 35.0

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