oj.uz

Submission #519875

# Submission time Handle Problem Language Result Execution time Memory
519875 2022-01-27T13:28:09 Z cig32 Road Construction (JOI21_road_construction) C++17
11 / 100
 204 ms 18596 KB 
#pragma GCC optimize("Ofast")
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2.5e5 + 10;
const int MOD = 1e9 + 7;
#define int long long

int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}

struct node{
  int val, idx;
} a[4*MAXN];
void init(int l, int r, int idx) {
  if(l == r) {
    a[idx].val = 0;
    a[idx].idx = l;
    return;
  }
  int mid = (l + r) >> 1;
  init(l, mid, 2*idx + 1);
  init(mid+1, r, 2*idx + 2);
}
void u(int l, int r, int tar, int idx, int val) {
  if(l == r) {
    a[idx].val = val;
    return;
  }
  int mid = (l + r) >> 1;
  if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
  else u(mid+1, r, tar, 2*idx+2, val);
  a[idx].val = min(a[2*idx+1].val, a[2*idx+2].val);
  a[idx].idx = (a[2*idx+1].val <= a[2*idx+2].val ? a[2*idx+1].idx : a[2*idx+2].idx);
}
pair<int, int> qu(int l, int r, int constl, int constr, int idx) {
  if(l<=constl && constr<=r) return {a[idx].val, a[idx].idx};
  int mid = (constl+constr) >> 1;
  if(mid<l || r<constl) return qu(l, r, mid+1, constr, 2*idx+2);
  else if(constr<l || r<mid+1) return qu(l, r, constl, mid, 2*idx+1);
  return min(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
}
int n, k, x[MAXN], y[MAXN];
void update(int i, int v) {
  u(1, n-1, i, 0, v);
}
int nxt[MAXN];
int query(int l, int r) {
  pair<int, int> res = qu(l, r, 1, n-1, 0);
  nxt[res.second]++;
  if(nxt[res.second] > n) {
    update(res.second, (int)1e18);
  }
  else {
    update(res.second, x[nxt[res.second]] - x[res.second]);
  }
  return res.first;
}
void solve(int tc) {
  cin >> n >> k;
  for(int i=1; i<=n; i++) {
    cin >> x[i] >> y[i];
  }
  if(n <= 1000) {
    vector<int> v;
    for(int i=1; i<=n; i++) {
      for(int j=i+1; j<=n; j++) {
        v.push_back(abs(x[i] - x[j]) + abs(y[i] - y[j]));
      }
    }
    sort(v.begin(), v.end());
    for(int i=0; i<k; i++) cout << v[i] << "\n";
    return;
  }
  for(int i=1; i<=n; i++) nxt[i] = i + 1;
  init(1, n-1, 0);
  sort(x+1, x+n+1);
  for(int i=1; i<n; i++) update(i, x[i+1] - x[i]);
  for(int i=0; i<k; i++) cout << query(1, n-1) << "\n";
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6972 KB Output is correct
2 Correct 70 ms 6980 KB Output is correct
3 Correct 57 ms 5052 KB Output is correct
4 Correct 39 ms 5140 KB Output is correct
5 Correct 58 ms 5836 KB Output is correct
6 Correct 20 ms 4548 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 15520 KB Output is correct
2 Correct 204 ms 18596 KB Output is correct
3 Correct 41 ms 4924 KB Output is correct
4 Correct 153 ms 18340 KB Output is correct
5 Correct 149 ms 18564 KB Output is correct
6 Correct 142 ms 18576 KB Output is correct
7 Correct 133 ms 17988 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 14380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 14380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6972 KB Output is correct
2 Correct 70 ms 6980 KB Output is correct
3 Correct 57 ms 5052 KB Output is correct
4 Correct 39 ms 5140 KB Output is correct
5 Correct 58 ms 5836 KB Output is correct
6 Correct 20 ms 4548 KB Output is correct
7 Incorrect 139 ms 10256 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6972 KB Output is correct
2 Correct 70 ms 6980 KB Output is correct
3 Correct 57 ms 5052 KB Output is correct
4 Correct 39 ms 5140 KB Output is correct
5 Correct 58 ms 5836 KB Output is correct
6 Correct 20 ms 4548 KB Output is correct
7 Correct 201 ms 15520 KB Output is correct
8 Correct 204 ms 18596 KB Output is correct
9 Correct 41 ms 4924 KB Output is correct
10 Correct 153 ms 18340 KB Output is correct
11 Correct 149 ms 18564 KB Output is correct
12 Correct 142 ms 18576 KB Output is correct
13 Correct 133 ms 17988 KB Output is correct
14 Incorrect 153 ms 14380 KB Output isn't correct
15 Halted 0 ms 0 KB -