oj.uz

Submission #925087

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

    long long find_prev(long long i, long long lx, long long 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() {
    long long N, K; cin >> N >> K;
    vector<pair<long long, long long>> p(N);
    for(long long i = 0; i < N; i++) cin >> p[i].first >> p[i].second;
    vector<long long> sx(N), sy(N);
    for(long long i = 0; i < N; i++) sx[i] = sy[i] = i;
    sort(sx.begin(), sx.end(), [&] (long long a, long long 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(), [&] (long long a, long long b) { return p[a].second == p[b].second ? p[a].first < p[b].first : p[a].second < p[b].second; });
    vector<long long> cx(N), cy(N);
    for(long long i = 0; i < N; i++) cx[sx[i]] = cy[sy[i]] = i;
    vector<long long> o1(N), o2(N);
    for(long long i = 0; i < N; i++) o1[i] = o2[i] = i;
    sort(o1.begin(), o1.end(), [&] (long long a, long long b) { return p[a].first + p[a].second < p[b].first + p[b].second; });
    sort(o2.begin(), o2.end(), [&] (long long a, long long b) { return p[a].first - p[a].second < p[b].first - p[b].second; });
    vector<pair<long long, long long>> c1(N), c2(N);
    for(long long i = 0; i < N; i++) c1[i] = {cx[o1[i]], cy[o1[i]]}, c2[i] = {cx[o2[i]], N - 1 - cy[o2[i]]};
    DS ds1(c1), ds2(c2);
    priority_queue<pair<long long, pair<long long, long long>>> pq1;
    priority_queue<pair<long long, pair<long long, long long>>> pq2;
    auto diff1 = [&] (long long i, long long j) {
        return (p[o1[i]].first + p[o1[i]].second) - (p[o1[j]].first + p[o1[j]].second);
    };
    auto diff2 = [&] (long long i, long long j) {
        return (p[o2[i]].first - p[o2[i]].second) - (p[o2[j]].first - p[o2[j]].second);
    };
    for(long long i = 0; i < N; i++) {
        long long n1 = ds1.find_prev(i, c1[i].first, c1[i].second);
        long long 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 << '\n';
            pq1.pop();
            long long 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 << '\n';
            pq2.pop();
            long long 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<long long int, long long int> >&)':
road_construction.cpp:16:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(long long i = 0; i < blocks.size(); i++) {
      |                              ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3156 KB Output is correct
2 Correct 47 ms 3072 KB Output is correct
3 Correct 43 ms 3132 KB Output is correct
4 Correct 43 ms 3252 KB Output is correct
5 Correct 49 ms 2136 KB Output is correct
6 Correct 2 ms 600 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2362 ms 2000764 KB Output is correct
2 Correct 2055 ms 2003664 KB Output is correct
3 Correct 39 ms 3044 KB Output is correct
4 Correct 1982 ms 2003484 KB Output is correct
5 Correct 1996 ms 2003940 KB Output is correct
6 Correct 1987 ms 2003828 KB Output is correct
7 Correct 2071 ms 2002956 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2378 ms 2010332 KB Output is correct
2 Correct 2386 ms 2011384 KB Output is correct
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2378 ms 2010332 KB Output is correct
2 Correct 2386 ms 2011384 KB Output is correct
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3156 KB Output is correct
2 Correct 47 ms 3072 KB Output is correct
3 Correct 43 ms 3132 KB Output is correct
4 Correct 43 ms 3252 KB Output is correct
5 Correct 49 ms 2136 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 775 ms 337004 KB Output is correct
8 Correct 781 ms 336540 KB Output is correct
9 Correct 42 ms 3152 KB Output is correct
10 Correct 580 ms 335552 KB Output is correct
11 Correct 584 ms 335404 KB Output is correct
12 Correct 697 ms 336660 KB Output is correct
13 Correct 673 ms 335640 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3156 KB Output is correct
2 Correct 47 ms 3072 KB Output is correct
3 Correct 43 ms 3132 KB Output is correct
4 Correct 43 ms 3252 KB Output is correct
5 Correct 49 ms 2136 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2362 ms 2000764 KB Output is correct
8 Correct 2055 ms 2003664 KB Output is correct
9 Correct 39 ms 3044 KB Output is correct
10 Correct 1982 ms 2003484 KB Output is correct
11 Correct 1996 ms 2003940 KB Output is correct
12 Correct 1987 ms 2003828 KB Output is correct
13 Correct 2071 ms 2002956 KB Output is correct
14 Correct 2378 ms 2010332 KB Output is correct
15 Correct 2386 ms 2011384 KB Output is correct
16 Runtime error 1 ms 348 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -