oj.uz

Submission #1071721

# Submission time Handle Problem Language Result Execution time Memory
1071721 2024-08-23T10:28:58 Z prvocislo Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 142932 KB 
// Lights, camera, b*tch smile, even when you wanna die
// He said he'd love me all his life
// But that life was too short

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

struct bod { ll x, y; };
bool cmpy(bod a, bod b) { return a.y < b.y; }
struct sgt2d
{
    int n;
    vector<vector<ll> > st, sx;
    vector<ll> cs;
    void init(vector<bod> v)
    {
        for (int i = 0; i < v.size(); i++) cs.push_back(v[i].x);
        sort(cs.begin(), cs.end()), cs.erase(unique(cs.begin(), cs.end()), cs.end());
        n = cs.size();
        st.assign(n * 2, {}), sx.assign(n * 2, {});
        sort(v.begin(), v.end(), cmpy);
        for (bod i : v)
        {
            int x = lower_bound(cs.begin(), cs.end(), i.x) - cs.begin();
            for (x += n; x > 0; x >>= 1) st[x].push_back(i.y), sx[x].push_back(i.x);
        }
    }
    int query(ll lx, ll rx, ll ly, ll ry)
    {
        lx = lower_bound(cs.begin(), cs.end(), lx) - cs.begin();
        rx = upper_bound(cs.begin(), cs.end(), rx) - cs.begin();
        int ans = 0;
        for (lx += n, rx += n; lx < rx; lx >>= 1, rx >>= 1)
        {
            if (lx & 1) ans += upper_bound(st[lx].begin(), st[lx].end(), ry) - lower_bound(st[lx].begin(), st[lx].end(), ly), lx++;
            if (rx & 1) rx--, ans += upper_bound(st[rx].begin(), st[rx].end(), ry) - lower_bound(st[rx].begin(), st[rx].end(), ly);
        }
        return ans;
    }
    void query2(ll lx, ll rx, ll ly, ll ry, vector<ll> &ans, bod b)
    {
        lx = lower_bound(cs.begin(), cs.end(), lx) - cs.begin();
        rx = upper_bound(cs.begin(), cs.end(), rx) - cs.begin();
        for (lx += n, rx += n; lx < rx; lx >>= 1, rx >>= 1)
        {
            if (lx & 1)
            {
                int li = lower_bound(st[lx].begin(), st[lx].end(), ly) - st[lx].begin();
                int ri = upper_bound(st[lx].begin(), st[lx].end(), ry) - st[lx].begin();
                for (int i = li; i < ri; i++) ans.push_back(max(abs(st[lx][i] - b.y), abs(sx[lx][i] - b.x)));
                lx++;
            }
            if (rx & 1)
            {
                rx--;
                int li = lower_bound(st[rx].begin(), st[rx].end(), ly) - st[rx].begin();
                int ri = upper_bound(st[rx].begin(), st[rx].end(), ry) - st[rx].begin();
                for (int i = li; i < ri; i++) ans.push_back(max(abs(st[rx][i] - b.y), abs(sx[rx][i] - b.x)));
            }
        }
    }
};
sgt2d st;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<bod> o(n), v(n);
    for (int i = 0; i < n; i++)
    {
        //o[i].x = rand() * 10000 + rand(), o[i].y = rand() * 10000 + rand();
        cin >> o[i].x >> o[i].y;
        v[i].x = o[i].x + o[i].y;
        v[i].y = o[i].x - o[i].y;
    }
    st.init(v);
    ll lo = 1, hi = 1e10;
    while (lo < hi)
    {
        ll mi = (lo + hi) / 2;
        ll cnt = 0;
        for (int i = 0; i < n; i++)
        {
            cnt += st.query(v[i].x - mi, v[i].x, v[i].y - mi, v[i].y) - 1;
            cnt += st.query(v[i].x - mi, v[i].x - 1, v[i].y + 1, v[i].y + mi);
        }
        if (cnt >= k) hi = mi;
        else lo = mi + 1;
    }
    vector<ll> ans;
    for (int i = 0; i < n; i++)
    {
        st.query2(v[i].x - lo + 1, v[i].x, v[i].y - lo + 1, v[i].y, ans, v[i]);
        st.query2(v[i].x - lo + 1, v[i].x - 1, v[i].y + 1, v[i].y + lo - 1, ans, v[i]);
    }
    sort(ans.begin(), ans.end(), greater<ll>());
    while (ans.size() && ans.back() == 0) ans.pop_back();
    reverse(ans.begin(), ans.end());
    while (ans.size() > k) ans.pop_back();
    while (ans.size() < k) ans.push_back(lo);
    for (int i = 0; i < k; i++) cout << ans[i] << "\n";
    return 0;
}

Compilation message

road_construction.cpp: In member function 'void sgt2d::init(std::vector<bod>)':
road_construction.cpp:21:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bod>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int i = 0; i < v.size(); i++) cs.push_back(v[i].x);
      |                         ~~^~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:105:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |     while (ans.size() > k) ans.pop_back();
      |            ~~~~~~~~~~~^~~
road_construction.cpp:106:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     while (ans.size() < k) ans.push_back(lo);
      |            ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5324 KB Output is correct
2 Correct 57 ms 5340 KB Output is correct
3 Correct 43 ms 5320 KB Output is correct
4 Correct 44 ms 5452 KB Output is correct
5 Correct 48 ms 4368 KB Output is correct
6 Correct 6 ms 604 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8255 ms 139776 KB Output is correct
2 Correct 8434 ms 139804 KB Output is correct
3 Correct 37 ms 5332 KB Output is correct
4 Correct 8032 ms 139656 KB Output is correct
5 Correct 8243 ms 139768 KB Output is correct
6 Correct 8521 ms 139896 KB Output is correct
7 Correct 8720 ms 139296 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10022 ms 142932 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 10022 ms 142932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5324 KB Output is correct
2 Correct 57 ms 5340 KB Output is correct
3 Correct 43 ms 5320 KB Output is correct
4 Correct 44 ms 5452 KB Output is correct
5 Correct 48 ms 4368 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Correct 6225 ms 59632 KB Output is correct
8 Correct 6527 ms 58996 KB Output is correct
9 Correct 45 ms 5316 KB Output is correct
10 Correct 5177 ms 64976 KB Output is correct
11 Correct 4539 ms 64332 KB Output is correct
12 Correct 1821 ms 32688 KB Output is correct
13 Correct 2800 ms 35516 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5324 KB Output is correct
2 Correct 57 ms 5340 KB Output is correct
3 Correct 43 ms 5320 KB Output is correct
4 Correct 44 ms 5452 KB Output is correct
5 Correct 48 ms 4368 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Correct 8255 ms 139776 KB Output is correct
8 Correct 8434 ms 139804 KB Output is correct
9 Correct 37 ms 5332 KB Output is correct
10 Correct 8032 ms 139656 KB Output is correct
11 Correct 8243 ms 139768 KB Output is correct
12 Correct 8521 ms 139896 KB Output is correct
13 Correct 8720 ms 139296 KB Output is correct
14 Execution timed out 10022 ms 142932 KB Time limit exceeded
15 Halted 0 ms 0 KB -