oj.uz

Submission #386365

# Submission time Handle Problem Language Result Execution time Memory
386365 2021-04-06T13:04:53 Z Mamnoon_Siam Road Construction (JOI21_road_construction) C++17
100 / 100
 5973 ms 18344 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
#define x first
#define y second
typedef pair<ll, ll> pt;

const int N = 250005;

int n, k;
pt a[N];
vi byX;
ll Ys[N]; int Ysz;
int lessY(ll y) {
  return int(lower_bound(Ys, Ys+Ysz, y) - Ys);
}
int ft[N];
void update(int pos, int val) {
  for(; pos < N; pos += pos & -pos) ft[pos] += val;
}
int query(int l, int r, int ret = 0) {
  for(l--; l > 0; l -= l & -l) ret -= ft[l];
  for(; r > 0; r -= r & -r) ret += ft[r];
  return ret;
}

ll count(ll d) {
  memset(ft, 0, sizeof ft);
  ll pairs = 0;
  int ptr = 1;
  for(int i = 1; i <= n; ++i) {
    while(a[ptr].x < a[i].x - d) {
      int j = lessY(a[ptr++].y) + 1;
      update(j, -1);
    }
    {
      int l = lessY(a[i].y - d) + 1;
      int r = lessY(a[i].y + d + 1);
      int me = lessY(a[i].y) + 1;
      pairs += query(l, r);
      update(me, +1);
    }
  }
  return pairs;
}

vector<ii> Less(ll d) {
  using pli = pair<ll, int>;
  set<pli> st;
  vector<ii> ret;
  int ptr = 1;
  for(int i = 1; i <= n; ++i) {
    while(a[ptr].x <= a[i].x - d) {
      st.erase(pli(a[ptr].y, ptr));
      ptr++;
    }
    auto lit = st.upper_bound(pli(a[i].y-d, INT_MAX));
    auto rit = st.lower_bound(pli(a[i].y+d, INT_MIN));
    for(auto it = lit; it != rit; ++it) {
      ret.emplace_back(i, it -> se);
    }
    st.insert(pli(a[i].y, i));
  }
  return ret;
}

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d %d", &n, &k);
  // assert(n <= 1000);
  // assert(k == 1);
  for(int i = 1; i <= n; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    a[i].x = x + y;
    a[i].y = x - y;
    Ys[i-1] = a[i].y;
  }
  sort(a+1, a+1+n);
  sort(Ys, Ys+n);
  Ysz = int(unique(Ys, Ys+n) - Ys);

  ll lo = 1, hi = 4000000000LL, low = -1;
  while(lo <= hi) {
    ll mid = (lo + hi) >> 1;
    if(count(mid) >= k) {
      low = mid;
      hi = mid-1;
    } else {
      lo = mid+1;
    }
  }
  auto les = Less(low);

  vector<ll> ans;
  for(auto [i, j] : les) {
    ans.emplace_back(max(abs(a[i].x - a[j].x), abs(a[i].y - a[j].y)));
  }
  for(int i = 0; i < k-sz(les); ++i) ans.emplace_back(low);
  sort(all(ans));

  for(ll x : ans) printf("%lld\n", x);
  return 0;
}

Compilation message

road_construction.cpp: In function 'int main(int, const char**)':
road_construction.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   scanf("%d %d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8040 KB Output is correct
2 Correct 70 ms 8040 KB Output is correct
3 Correct 65 ms 8152 KB Output is correct
4 Correct 63 ms 8040 KB Output is correct
5 Correct 65 ms 6904 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2307 ms 15496 KB Output is correct
2 Correct 2302 ms 15548 KB Output is correct
3 Correct 60 ms 7928 KB Output is correct
4 Correct 2312 ms 15240 KB Output is correct
5 Correct 2297 ms 15452 KB Output is correct
6 Correct 2276 ms 15524 KB Output is correct
7 Correct 2231 ms 15488 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5185 ms 12328 KB Output is correct
2 Correct 5154 ms 12312 KB Output is correct
3 Correct 3 ms 1260 KB Output is correct
4 Correct 2213 ms 10092 KB Output is correct
5 Correct 2033 ms 12656 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5185 ms 12328 KB Output is correct
2 Correct 5154 ms 12312 KB Output is correct
3 Correct 3 ms 1260 KB Output is correct
4 Correct 2213 ms 10092 KB Output is correct
5 Correct 2033 ms 12656 KB Output is correct
6 Correct 5119 ms 12312 KB Output is correct
7 Correct 5239 ms 12312 KB Output is correct
8 Correct 3 ms 1260 KB Output is correct
9 Correct 3 ms 1260 KB Output is correct
10 Correct 5149 ms 12312 KB Output is correct
11 Correct 2250 ms 10092 KB Output is correct
12 Correct 2051 ms 12560 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8040 KB Output is correct
2 Correct 70 ms 8040 KB Output is correct
3 Correct 65 ms 8152 KB Output is correct
4 Correct 63 ms 8040 KB Output is correct
5 Correct 65 ms 6904 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 2143 ms 11900 KB Output is correct
8 Correct 2137 ms 11772 KB Output is correct
9 Correct 64 ms 8040 KB Output is correct
10 Correct 1985 ms 11160 KB Output is correct
11 Correct 1791 ms 11112 KB Output is correct
12 Correct 680 ms 9820 KB Output is correct
13 Correct 821 ms 10844 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8040 KB Output is correct
2 Correct 70 ms 8040 KB Output is correct
3 Correct 65 ms 8152 KB Output is correct
4 Correct 63 ms 8040 KB Output is correct
5 Correct 65 ms 6904 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 2307 ms 15496 KB Output is correct
8 Correct 2302 ms 15548 KB Output is correct
9 Correct 60 ms 7928 KB Output is correct
10 Correct 2312 ms 15240 KB Output is correct
11 Correct 2297 ms 15452 KB Output is correct
12 Correct 2276 ms 15524 KB Output is correct
13 Correct 2231 ms 15488 KB Output is correct
14 Correct 5185 ms 12328 KB Output is correct
15 Correct 5154 ms 12312 KB Output is correct
16 Correct 3 ms 1260 KB Output is correct
17 Correct 2213 ms 10092 KB Output is correct
18 Correct 2033 ms 12656 KB Output is correct
19 Correct 5119 ms 12312 KB Output is correct
20 Correct 5239 ms 12312 KB Output is correct
21 Correct 3 ms 1260 KB Output is correct
22 Correct 3 ms 1260 KB Output is correct
23 Correct 5149 ms 12312 KB Output is correct
24 Correct 2250 ms 10092 KB Output is correct
25 Correct 2051 ms 12560 KB Output is correct
26 Correct 2143 ms 11900 KB Output is correct
27 Correct 2137 ms 11772 KB Output is correct
28 Correct 64 ms 8040 KB Output is correct
29 Correct 1985 ms 11160 KB Output is correct
30 Correct 1791 ms 11112 KB Output is correct
31 Correct 680 ms 9820 KB Output is correct
32 Correct 821 ms 10844 KB Output is correct
33 Correct 5947 ms 18344 KB Output is correct
34 Correct 5973 ms 18316 KB Output is correct
35 Correct 5215 ms 17656 KB Output is correct
36 Correct 1761 ms 16476 KB Output is correct
37 Correct 1807 ms 16476 KB Output is correct
38 Correct 2263 ms 17500 KB Output is correct