답안 #1080877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080877	2024-08-29T15:29:44 Z	binminh01	Road Construction (JOI21_road_construction)	C++17	100 / 100	6911 ms	46868 KB

road_construction

#include<bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define double long double
#define gcd __gcd
#define lcm(a, b) ((a)/gcd(a, b)*(b))
#define sqrt sqrtl
#define log2 log2l
#define log10 log10l
#define floor floorl
#define to_string str
#define yes cout << "YES"
#define no cout << "NO"
#define trav(i, a) for (auto &i: (a))
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)a.size()
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define Find(a, n) (find(all(a), n) - a.begin())
#define Count(a, n) count(all(a), n)
#define Upper(a, n) (upper_bound(all(a), n) - a.begin())
#define Lower(a, n) (lower_bound(all(a), n) - a.begin())
#define next_perm(a) next_permutation(all(a))
#define prev_perm(a) prev_permutation(all(a))
#define sorted(a) is_sorted(all(a))
#define sum(a) accumulate(all(a), 0)
#define sumll(a) accumulate(all(a), 0ll)
#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define Unique(a) Sort(a), (a).resize(unique(all(a)) - a.begin())
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __buitlin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define fileopen(s) open((string(s) + ".inp").c_str()), write((string(s) + ".out").c_str());
#define For(i, a, b) for (auto i = (a); i < (b); i++)
#define Fore(i, a, b) for (auto i = (a); i >= (b); i--)
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ret(s) return void(cout << s);

const int mod = 1e9 + 7, mod2 = 998244353;
const double PI = acos(-1), eps = 1e-9;
const ull npos = string::npos;
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using cd = complex<double>;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vdo;
typedef vector<vdo> vvdo;
typedef vector<string> vs;
typedef vector<pii> vpair;
typedef vector<vpair> vvpair;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<cd> vcd;
typedef priority_queue<int> pq;
typedef priority_queue<int, vi, greater<int>> pqg;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vll, greater<ll>> pqgll;

ll add(ll a, ll b, int m) {if (a >= m) a%=m;if (b >= m) b%=m;a+=b;return a >= m ? a - m: a;}
ll sub(ll a, ll b, int m) {if (a >= m) a%=m;if (b >= m) b%=m;a-=b;return a < 0 ? a + m: a;}
ll mul(ll a, ll b, int m) {if (a >= m) a%=m;if (b >= m) b%=m;return a*b % m;}
ll bin_mul(ll a, ll b, ll m) {if (a >= m) a%=m;if (b >= m) b%=m;ll x = 0;while (b) {if (b & 1) x = (x + a) % m;a = (a + a) % m;b>>=1;}return x;}
ll power(ll a, ll b, int m) {ll x = 1;if (a >= m) a%=m; while (b) {if (b & 1) x = x*a % m;a = a*a % m;b>>=1;}return x;}
ll power(ll a, ll b) {ll x = 1;while (b) {if (b & 1) x = x*a;a = a*a;b>>=1;}return x;}
ll ceil(ll a, ll b) {return (a + b - 1)/b;}
ll to_int(const string &s) {ll x = 0; for (int i = (s[0] == '-'); i < sz(s); i++) x = x*10 + s[i] - '0';return x*(s[0] == '-' ? -1: 1);}
bool is_prime(ll n) {if (n < 2) return 0;if (n < 4) return 1;if (n % 2 == 0 || n % 3 == 0) return 0;for (ll i = 5; i*i <= n; i+=6) {if(n % i == 0 || n % (i + 2) == 0) return 0;}return 1;}
bool is_square(ll n) {ll k = sqrt(n); return k*k == n;}
ll factorial(int n) {ll x = 1;for (int i = 2; i <= n; i++) x*=i;return x;}
ll factorial(int n, int m) {ll x = 1;for (ll i = 2; i <= n; i++) x = x*i % m;return x;}
bool is_power(ll n, ll k) {while (n % k == 0) n/=k;return n == 1ll;}
string str(ll n) {if (n == 0) return "0"; string s = ""; bool c = 0; if (n < 0) c = 1, n = -n; while (n) {s+=n % 10 + '0'; n/=10;} if (c) s+='-'; Reverse(s); return s;}
string repeat(const string &s, int n) {if (n < 0) return ""; string x = ""; while (n--) x+=s; return x;}
string bin(ll n) {string s = ""; while (n) {s+=(n & 1) + '0'; n>>=1;} Reverse(s); return s;}
void sieve(vector<bool> &a) {int n = a.size(); a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(bool a[], int n) {a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(vector<int> &a) {int n = a.size(); for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
void sieve(int a[], int n) {for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
vector<pii> factorize(int n) {vector<pii> a; for (int i = 2; i*i <= n; i++) {if (n % i == 0) {int k = 0; while (n % i == 0) k++, n/=i; a.emplace_back(i, k);}} if (n > 1) a.emplace_back(n, 1); return a;}
int rand(int l, int r) {return uniform_int_distribution<int>(l, r)(mt);}
int Log2(int n) {return 31 - __builtin_clz(n);}
template<class T> void compress(vector<T> &a) {vector<T> b; for (T &i: a) b.push_back(i); sort(all(b)); b.resize(unique(all(b)) - b.begin()); for (T &i: a) i = lower_bound(all(b), i) - b.begin() + 1;}

template<class A, class B> istream& operator>>(istream& in, pair<A, B> &p) {in >> p.first >> p.second; return in;}
template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &p) {out << p.first << ' ' << p.second; return out;}
template<class T> istream& operator>>(istream& in, vector<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<T> &a) {for (auto &i: a) out << i << ' '; return out;}
template<class T> istream& operator>>(istream& in, vector<vector<T>> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<vector<T>> &a) {for (auto &i: a) out << i << '\n'; return out;}
template<class T> istream& operator>>(istream& in, deque<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const deque<T> &a) {for (auto &i: a) out << i << ' '; return out;}
// istream& operator>>(istream& in, __int128_t &a) {string s; in >> s; a = 0; for (auto &i: s) a = a*10 + (i - '0'); return in;}
// ostream& operator<<(ostream& out, __int128_t a) {string s = ""; while (a > 0) {s+=(int)(a % 10) + '0'; a/=10;} Reverse(s); out << s; return out;}

struct que {
    ll s, l, r; int o;
    que(ll s = 0, ll l = 0, ll r = 0, int o = 0): s(s), l(l), r(r), o(o) {}
};
const int N = 750005;
int B[N];
void upd(int i) {
    for (; i < N; i+=i & (-i)) B[i]++;
}
int get(int i) {
    int x = 0;
    for (; i; i-=i & (-i)) x+=B[i];
    return x;
}
int get(int l, int r) {
    return get(r) - get(l - 1);
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cout << fixed << setprecision(10);
    int n, k; cin >> n >> k;
    vector<pll> a(n);
    vll c;
    For(i,0,n) cin >> a[i], a[i] = {a[i].first - a[i].second, a[i].first + a[i].second}, c.pb(a[i].second);
    Sort(a); Unique(c);
    ll l = 0, r = 4e9;
    while (l < r) {
        memset(B, 0, sizeof(B));
        ll m = (l + r) >> 1;
        vector<que> t;
        For(i,0,n){
            auto [x, y] = a[i];
            t.eb(x + m, y - m, y + m, 1);
            t.eb(x - m - 1, y - m, y + m, -1);
        }
        sort(all(t), [](que x, que y){
            return x.s < y.s;
        });
        int i = 0, x = 0;
        for (auto [s, l, r, o]: t) {
            while (i < n && a[i].first <= s) upd(Lower(c, a[i].second) + 1), i++;
            x+=get(Lower(c, l) + 1, Upper(c, r))*o;
            if ((x - n)/2 >= k) break;
        }
        if ((x - n)/2 < k) l = m + 1;
        else r = m;
    }
    ll R = l - 1, L = l;
    set<pll> x, y;
    vector<que> t;
    For(i,0,n){
        auto [x, y] = a[i];
        t.eb(x + R, y - R, y + R, i);
    }
    sort(all(t), [](que x, que y){
        return x.s < y.s;
    });
    int i = 0;
    vll w;
    set<pair<pll, pll>> z;
    for (auto [s, l, r, j]: t) {
        while (i < n && a[i].first <= s) x.insert(a[i]), y.emplace(a[i].second, a[i].first), i++;
        while (sz(x) && x.begin()->first < s - 2*R) {
            y.erase({x.begin()->second, x.begin()->first}), x.erase(x.begin());
        }
        auto u = y.lower_bound({l, -1e18}), v = y.lower_bound({r + 1, -1e18});
        for (; u != v; u++) {
            if (a[j].first == u->second && a[j].second == u->first) continue;
            if (z.count({{u->second, u->first}, a[j]})) continue;
            z.insert({a[j], {u->second, u->first}});
            w.pb(max(abs(a[j].first - u->second), abs(a[j].second - u->first)));
        }
    }
    Sort(w);
    while (sz(w) < k) w.pb(L);
    trav(j,w) cout << j << '\n';
    cerr << "\nProcess returned 0 (0x0)   execution time :  " << 0.001*clock() << " s";
    return 0;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	166 ms	27584 KB	Output is correct
2	Correct	166 ms	27496 KB	Output is correct
3	Correct	179 ms	27584 KB	Output is correct
4	Correct	154 ms	27576 KB	Output is correct
5	Correct	167 ms	26304 KB	Output is correct
6	Correct	8 ms	3420 KB	Output is correct

Subtask #2

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2353 ms	41404 KB	Output is correct
2	Correct	2353 ms	43948 KB	Output is correct
3	Correct	173 ms	27808 KB	Output is correct
4	Correct	2405 ms	43968 KB	Output is correct
5	Correct	2399 ms	44540 KB	Output is correct
6	Correct	2392 ms	44448 KB	Output is correct
7	Correct	2000 ms	44632 KB	Output is correct

Subtask #3

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5236 ms	41404 KB	Output is correct
2	Correct	5291 ms	45496 KB	Output is correct
3	Correct	3 ms	3164 KB	Output is correct
4	Correct	2096 ms	44216 KB	Output is correct
5	Correct	2169 ms	46716 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5236 ms	41404 KB	Output is correct
2	Correct	5291 ms	45496 KB	Output is correct
3	Correct	3 ms	3164 KB	Output is correct
4	Correct	2096 ms	44216 KB	Output is correct
5	Correct	2169 ms	46716 KB	Output is correct
6	Correct	5195 ms	46476 KB	Output is correct
7	Correct	5403 ms	46468 KB	Output is correct
8	Correct	3 ms	3164 KB	Output is correct
9	Correct	3 ms	3164 KB	Output is correct
10	Correct	5106 ms	46472 KB	Output is correct
11	Correct	1961 ms	44328 KB	Output is correct
12	Correct	2175 ms	46868 KB	Output is correct

Subtask #5

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	166 ms	27584 KB	Output is correct
2	Correct	166 ms	27496 KB	Output is correct
3	Correct	179 ms	27584 KB	Output is correct
4	Correct	154 ms	27576 KB	Output is correct
5	Correct	167 ms	26304 KB	Output is correct
6	Correct	8 ms	3420 KB	Output is correct
7	Correct	2543 ms	32276 KB	Output is correct
8	Correct	2442 ms	34272 KB	Output is correct
9	Correct	175 ms	27584 KB	Output is correct
10	Correct	2127 ms	33672 KB	Output is correct
11	Correct	1410 ms	34068 KB	Output is correct
12	Correct	823 ms	22260 KB	Output is correct
13	Correct	928 ms	33020 KB	Output is correct

Subtask #6

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	166 ms	27584 KB	Output is correct
2	Correct	166 ms	27496 KB	Output is correct
3	Correct	179 ms	27584 KB	Output is correct
4	Correct	154 ms	27576 KB	Output is correct
5	Correct	167 ms	26304 KB	Output is correct
6	Correct	8 ms	3420 KB	Output is correct
7	Correct	2353 ms	41404 KB	Output is correct
8	Correct	2353 ms	43948 KB	Output is correct
9	Correct	173 ms	27808 KB	Output is correct
10	Correct	2405 ms	43968 KB	Output is correct
11	Correct	2399 ms	44540 KB	Output is correct
12	Correct	2392 ms	44448 KB	Output is correct
13	Correct	2000 ms	44632 KB	Output is correct
14	Correct	5236 ms	41404 KB	Output is correct
15	Correct	5291 ms	45496 KB	Output is correct
16	Correct	3 ms	3164 KB	Output is correct
17	Correct	2096 ms	44216 KB	Output is correct
18	Correct	2169 ms	46716 KB	Output is correct
19	Correct	5195 ms	46476 KB	Output is correct
20	Correct	5403 ms	46468 KB	Output is correct
21	Correct	3 ms	3164 KB	Output is correct
22	Correct	3 ms	3164 KB	Output is correct
23	Correct	5106 ms	46472 KB	Output is correct
24	Correct	1961 ms	44328 KB	Output is correct
25	Correct	2175 ms	46868 KB	Output is correct
26	Correct	2543 ms	32276 KB	Output is correct
27	Correct	2442 ms	34272 KB	Output is correct
28	Correct	175 ms	27584 KB	Output is correct
29	Correct	2127 ms	33672 KB	Output is correct
30	Correct	1410 ms	34068 KB	Output is correct
31	Correct	823 ms	22260 KB	Output is correct
32	Correct	928 ms	33020 KB	Output is correct
33	Correct	6777 ms	46648 KB	Output is correct
34	Correct	6911 ms	46484 KB	Output is correct
35	Correct	5604 ms	46464 KB	Output is correct
36	Correct	2286 ms	46768 KB	Output is correct
37	Correct	2328 ms	46472 KB	Output is correct
38	Correct	2279 ms	46724 KB	Output is correct