제출 #1080321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080321		Thanhs	Road Construction (JOI21_road_construction)	C++14	100 / 100	4742 ms	36116 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define aint(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e6 + 5;

int n;

struct BIT
{
    int dt[NM];
    void reset()
    {
        memset(dt, 0, sizeof dt);
    }
    void upd(int i, int v)
    {
        for (; i < NM; i += i & -i)
            dt[i] += v;
    }
    int get(int i)
    {
        if (i < 0)
            return 0;
        int res = 0;
        for (; i; i -= i & -i)
            res += dt[i];
        return res;
    }
    int get(int l, int r)
    {
        return get(r) - get(l - 1);
    }
}bit;

int k;
vector<int> nen;
pair<int, int> a[NM];

int find(int x)
{
    return lower_bound(nen.begin(), nen.end(), x) - nen.begin() + 1;
}

int check(int x)
{
    bit.reset();
    int pt = 1, res = 0;
    for (int i = 1; i <= n; i++)
    {
        while (pt < i && a[pt].fi < a[i].fi - x)
            bit.upd(find(a[pt++].se), -1);
        res += bit.get(find(a[i].se - x), find(a[i].se + x + 1) - 1);
        bit.upd(find(a[i].se), 1);
    }
    return res;
}

map<int, int> mp;
set<pair<int, int>> s;

int dist(int i, int j)
{
    return max(abs(a[i].fi - a[j].fi), abs(a[i].se - a[j].se));
}

void trace(int x)
{
    int pt = 1;
    for (int i = 1; i <= n; i++)
    {
        while (pt < i && a[pt].fi < a[i].fi - x)
            s.erase({a[pt].se, pt++});
        auto it = s.lower_bound({a[i].se - x, 0});
        while (it != s.end() && (*it).fi <= a[i].se + x)
        {
            mp[dist((*it).se, i)]++;
            it = next(it);
        }
        s.insert({a[i].se, i});
    }
    for (auto p : mp)
    {
        for (int i = 0; i < p.se; i++)
            cout << p.fi << endl;
        k -= p.se;
    }
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fi >> a[i].se;
        a[i].fi += a[i].se;
        a[i].se = a[i].fi - 2 * a[i].se;
        nen.push_back(a[i].se);
    }
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    sort(a + 1, a + 1 + n);
    int l = -1, r = 5e9;
    while (l < r - 1)
    {
        int m = l + r >> 1;
        if (check(m) >= k)
            r = m;
        else
            l = m;
    }
    trace(r - 1);
    for (int i = 1; i <= k; i++)
        cout << r << endl;
}

signed main()
{
    fastIO
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1; // cin >> tc;
    while (tc--)
        solve();

}

컴파일 시 표준 에러 (stderr) 메시지

road_construction.cpp: In function 'void trace(long long int)':
road_construction.cpp:86:34: warning: operation on 'pt' may be undefined [-Wsequence-point]
   86 |             s.erase({a[pt].se, pt++});
      |                                ~~^~
road_construction.cpp:86:34: warning: operation on 'pt' may be undefined [-Wsequence-point]
road_construction.cpp: In function 'void solve()':
road_construction.cpp:119:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |         int m = l + r >> 1;
      |                 ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35