oj.uz

Submission #447899

# Submission time Handle Problem Language Result Execution time Memory
447899 2021-07-28T05:06:21 Z blue Road Construction (JOI21_road_construction) C++17
5 / 100
 10000 ms 58256 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
 
const long long INF = 1'000'000'000'000LL;
const int maxN = 250000;
 
struct segtree
{
    int l;
    int r;
    pair<int, long long> v; //range max
 
    segtree* left = NULL;
    segtree* right = NULL;
 
    segtree()
    {
        ;
    }
 
    segtree(int L, int R)
    {
        l = L;
        r = R;
        v = make_pair(l, -INF);
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }
 
    void update(int I, long long V)
    {
        if(I < l || r < I) return;
        else if(l == r) v = make_pair(l, V);
        else
        {
            left->update(I, V);
            right->update(I, V);
 
            pair<int, long long> LP = left->v;
            pair<int, long long> RP = right->v;
 
            if(LP.second > RP.second) v = LP;
            else v = RP;
        }
    }
 
    pair<int, long long> rangemax(int L, int R)
    {
        if(R < l || r < L) return make_pair(-1, -INF);
        else if(L <= l && r <= R) return v;
        else
        {
            pair<int, long long> LP = left->rangemax(L, R);
            pair<int, long long> RP = right->rangemax(L, R);
 
            if(LP.second > RP.second) return LP;
            else return RP;
        }
    }
};
 
int N, K;
 
struct point
{
    long long X;
    long long Y;
    int Yindex;
};
 
vector<point> P;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N >> K;
 
    P = vector<point>(N);
 
    for(int i = 0; i < N; i++) cin >> P[i].X >> P[i].Y;
 
    sort(P.begin(), P.end(), [] (point A, point B)
    {
        return A.Y < B.Y;
    });
 
    for(int i = 0; i < N; i++) P[i].Yindex = i+1;
 
    sort(P.begin(), P.end(), [] (point A, point B)
    {
        return A.X < B.X;
    });
 
    // for(point p:P) cerr << p.X << ' ' << p.Y << ' ' << p.Yindex << '\n';
 
    segtree S(1, N), T(1, N);
 
    long long lo = 0, hi = 4'000'000'000LL;
    vector<long long> res;
    while(1)
    {
        long long Kval = (lo+hi)/2;
        res.clear();
        for(int i = 1; i <= N; i++)
        {
            S.update(i, -INF);
            T.update(i, -INF);
        }
 
        // cerr << "searching " << lo << ' ' << hi << '\n';
 
 
        for(point p:P)
        {
            vector< pair<int, long long> > updates;
 
            while(res.size() < K+1)
            {
                pair<int, long long> Q = S.rangemax(1, p.Yindex);
                if(Q.second <= -INF) break;
 
                if((p.X + p.Y) - Q.second > Kval) break;
 
                res.push_back((p.X + p.Y) - Q.second);
 
                S.update(Q.first, -INF);
 
                updates.push_back(Q);
            }
 
            for(pair<int, long long> u: updates)
                S.update(u.first, u.second);
 
            updates.clear();
 
 
 
 
 
 
            while(res.size() < K+1)
            {
                pair<int, long long> Q = T.rangemax(p.Yindex+1, N);
                if(Q.second <= -INF) break;
 
                if((p.X - p.Y) - Q.second > Kval) break;
 
                res.push_back((p.X - p.Y) - Q.second);
 
                T.update(Q.first, -INF);
 
                updates.push_back(Q);
            }
 
            for(pair<int, long long> u: updates)
                T.update(u.first, u.second);
 
            updates.clear();
 
 
 
 
 
 
            S.update(p.Yindex, p.X + p.Y);
            T.update(p.Yindex, p.X - p.Y);
 
 
        }
 
        sort(res.begin(), res.end());
        if(lo == hi)
        {
            while(res.size() > K) res.pop_back();
            break;
        }
        else if(res.size() >= K) hi = Kval;
        else lo = Kval + 1;
    }
    for(long long r:res) cout << r << '\n';
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:125:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |             while(res.size() < K+1)
      |                   ~~~~~~~~~~~^~~~~
road_construction.cpp:149:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  149 |             while(res.size() < K+1)
      |                   ~~~~~~~~~~~^~~~~
road_construction.cpp:182:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  182 |             while(res.size() > K) res.pop_back();
      |                   ~~~~~~~~~~~^~~
road_construction.cpp:185:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  185 |         else if(res.size() >= K) hi = Kval;
      |                 ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3327 ms 5200 KB Output is correct
2 Correct 3364 ms 5184 KB Output is correct
3 Correct 3169 ms 5248 KB Output is correct
4 Correct 2899 ms 5368 KB Output is correct
5 Correct 3230 ms 4036 KB Output is correct
6 Correct 41 ms 556 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10065 ms 58256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10087 ms 58128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10087 ms 58128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3327 ms 5200 KB Output is correct
2 Correct 3364 ms 5184 KB Output is correct
3 Correct 3169 ms 5248 KB Output is correct
4 Correct 2899 ms 5368 KB Output is correct
5 Correct 3230 ms 4036 KB Output is correct
6 Correct 41 ms 556 KB Output is correct
7 Execution timed out 10007 ms 25596 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3327 ms 5200 KB Output is correct
2 Correct 3364 ms 5184 KB Output is correct
3 Correct 3169 ms 5248 KB Output is correct
4 Correct 2899 ms 5368 KB Output is correct
5 Correct 3230 ms 4036 KB Output is correct
6 Correct 41 ms 556 KB Output is correct
7 Execution timed out 10065 ms 58256 KB Time limit exceeded
8 Halted 0 ms 0 KB -