oj.uz

Submission #432291

# Submission time Handle Problem Language Result Execution time Memory
432291 2021-06-18T07:28:53 Z blue Road Construction (JOI21_road_construction) C++17
11 / 100
 10000 ms 56500 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

long long long_absval(long long x)
{
    return max(x, -x);
}

const int maxN = 250000;
const long long INF = 1'000'000'000'000'000'000LL;

vector<long long> A(1+maxN), B(1+maxN);
vector<int> I_A, I_B;

int N, K;

struct loc
{
    int i;
    long long v;
};

bool operator < (loc P, loc Q)
{
    if(P.v == Q.v) return P.i < Q.i;
    return P.v < Q.v;
}


vector<int> nxtA, nxtB;
vector<long long> valA, valB;

void compute_score_A(int i)
{
    valA[i] = INF;
    if(nxtA[i] <= N-1)
    {
        valA[i] = A[ I_A[nxtA[i]] ] - A[ I_A[i] ];
    }
}

void compute_score_B(int i)
{
    valB[i] = INF;

    if(nxtB[i] <= N-1)
    {
        valB[i] = B[ I_B[nxtB[i]] ] - B[ I_B[i] ];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K;

    for(int i = 1; i <= N; i++)
    {
        long long X, Y;
        cin >> X >> Y;
        A[i] = X+Y;
        B[i] = X-Y;
    }

    I_A = I_B = vector<int>(N);
    for(int i = 0; i < N; i++)
    {
        I_A[i] = i+1;
        I_B[i] = i+1;
    }

    sort(I_A.begin(), I_A.end(), [] (int p, int q)
    {
        return A[p] < A[q];
    });

    sort(I_B.begin(), I_B.end(), [] (int p, int q)
    {
        return B[p] < B[q];
    });

    multiset<long long> res;







    nxtA = vector<int>(N);
    for(int i = 0; i < N; i++)
    {
        nxtA[i] = i+1;
    }

    valA = vector<long long>(N, INF);
    for(int i = 0; i < N; i++)
    {
        compute_score_A(i);
    }
    set<loc> LA;
    for(int i = 0; i < N; i++) LA.insert(loc{i, valA[i]});









    nxtB = vector<int>(N);
    for(int i = 0; i < N; i++)
    {
        nxtB[i] = i+1;
    }

    valB = vector<long long>(N, INF);
    for(int i = 0; i < N; i++)
    {
        compute_score_B(i);
    }

    set<loc> LB;
    for(int i = 0; i < N; i++) LB.insert(loc{i, valB[i]});






    while(res.size() < K)
    {
        if(valA[LA.begin()->i] < valB[LB.begin()->i])
        {
            int i = LA.begin()->i;

            LA.erase(LA.begin());

            int j = nxtA[i];

            if(long_absval(A[ I_A[i] ] - A[ I_A[j] ]) >= long_absval(B[ I_A[i] ] - B[ I_A[j] ]))
            {
                res.insert(long_absval(A[ I_A[i] ] - A[ I_A[j] ]));
                // cerr << I_A[i] << ' ' << I_A[j] << ' ' << abs(A[ I_A[i] ] - A[ I_A[j] ]) << '\n';
            }
            nxtA[i]++;
            compute_score_A(i);

            LA.insert(loc{i, valA[i]});
        }
        else
        {
            int i = LB.begin()->i;

            LB.erase(LB.begin());

            int j = nxtB[i];

            // cerr << i << ' ' << val[i] << ' ' << nxt[i] << '\n';

            if(long_absval(B[ I_B[i] ] - B[ I_B[j] ]) > long_absval(A[ I_B[i] ] - A[ I_B[j] ]))
            {
                res.insert(long_absval(B[ I_B[i] ] - B[ I_B[j] ]));
                // cerr << I_B[i] << ' ' << I_B[j] << ' ' << abs(B[ I_B[i] ] - B[ I_B[j] ]) << '\n';
            }
            nxtB[i]++;
            compute_score_B(i);

            LB.insert(loc{i, valB[i]});
        }
    }







    int ct = 0;
    for(long long r:res)
    {
        ct++;
        if(ct > K) break;
        cout << r << '\n';
    }
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:138:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  138 |     while(res.size() < K)
      |           ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 18780 KB Output is correct
2 Correct 269 ms 18624 KB Output is correct
3 Correct 213 ms 18704 KB Output is correct
4 Correct 220 ms 18636 KB Output is correct
5 Correct 225 ms 17520 KB Output is correct
6 Correct 10 ms 4428 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1647 ms 56344 KB Output is correct
2 Correct 1621 ms 56308 KB Output is correct
3 Correct 205 ms 18500 KB Output is correct
4 Correct 584 ms 56072 KB Output is correct
5 Correct 708 ms 56500 KB Output is correct
6 Correct 749 ms 56384 KB Output is correct
7 Correct 672 ms 55616 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 43396 KB Output is correct
2 Correct 1494 ms 43376 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 365 ms 43384 KB Output is correct
5 Execution timed out 10024 ms 43268 KB Time limit exceeded

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 43396 KB Output is correct
2 Correct 1494 ms 43376 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 365 ms 43384 KB Output is correct
5 Execution timed out 10024 ms 43268 KB Time limit exceeded

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 18780 KB Output is correct
2 Correct 269 ms 18624 KB Output is correct
3 Correct 213 ms 18704 KB Output is correct
4 Correct 220 ms 18636 KB Output is correct
5 Correct 225 ms 17520 KB Output is correct
6 Correct 10 ms 4428 KB Output is correct
7 Execution timed out 10036 ms 19996 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 18780 KB Output is correct
2 Correct 269 ms 18624 KB Output is correct
3 Correct 213 ms 18704 KB Output is correct
4 Correct 220 ms 18636 KB Output is correct
5 Correct 225 ms 17520 KB Output is correct
6 Correct 10 ms 4428 KB Output is correct
7 Correct 1647 ms 56344 KB Output is correct
8 Correct 1621 ms 56308 KB Output is correct
9 Correct 205 ms 18500 KB Output is correct
10 Correct 584 ms 56072 KB Output is correct
11 Correct 708 ms 56500 KB Output is correct
12 Correct 749 ms 56384 KB Output is correct
13 Correct 672 ms 55616 KB Output is correct
14 Correct 1102 ms 43396 KB Output is correct
15 Correct 1494 ms 43376 KB Output is correct
16 Correct 3 ms 4172 KB Output is correct
17 Correct 365 ms 43384 KB Output is correct
18 Execution timed out 10024 ms 43268 KB Time limit exceeded