oj.uz

Submission #263166

# Submission time Handle Problem Language Result Execution time Memory
263166 2020-08-13T13:46:36 Z Haunted_Cpp Swimming competition (LMIO18_plaukimo_varzybos) C++17
30 / 100
 2000 ms 79304 KB 
/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//~ #pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif
 
class SegmentTree {
private:
  const int LO, HI;
  struct Node {
    int mn;
    int lazy;
    Node () {
      mn = 1e9;
      lazy = 0;
    }
  };
  vector<Node> seg;
  void push(int l, int r, int node) {
    if (seg[node].lazy == 0) return;
    seg[node].mn += seg[node].lazy;
    if (l != r) {
      seg[2 * node + 1].lazy += seg[node].lazy;
      seg[2 * node + 2].lazy += seg[node].lazy;
    }
    seg[node].lazy = 0;
  }
  void modify(int where, int delta, int l, int r, int node) {
    push(l, r, node);
    if (l > where || r < where) return;
    if (l >= where && r <= where) {
      seg[node].mn = delta;
      return;
    }
    const int mid = l + (r - l) / 2;
    modify(where, delta, l, mid, 2 * node + 1);
    modify(where, delta, mid + 1, r, 2 * node + 2);
    seg[node].mn = min(seg[2 * node + 1].mn, seg[2 * node + 2].mn);
  }
  void range_update(int ql, int qr, int delta, int l, int r, int node) {
    push(l, r, node);
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {
      seg[node].lazy = delta;
      push(l, r, node);
      return;
    }
    const int mid = l + (r - l) / 2;
    range_update(ql, qr, delta, l, mid, 2 * node + 1);
    range_update(ql, qr, delta, mid + 1, r, 2 * node + 2);
    seg[node].mn = min(seg[2 * node + 1].mn, seg[2 * node + 2].mn);
  }
    
  int query(int ql, int qr, int l, int r, int node) {
    push(l, r, node);
    if (l > qr || r < ql) return 1e9;
    if (l >= ql && r <= qr) return seg[node].mn;
    const int mid = l + (r - l) / 2;
    return min(query(ql, qr, l, mid, 2 * node + 1), query(ql, qr, mid + 1, r, 2 * node + 2));
  }
public:
  SegmentTree(int n) : LO(0), HI(n - 1) {
    seg.resize(4 * n);
  }
  void modify(int where, int delta) {
    modify(where, delta, LO, HI, 0);
  }
  void range_update(int ql, int qr, int delta) {
    ql = max(ql, 0);
    range_update(ql, qr, delta, LO, HI, 0);
  }
  int query(int ql, int qr) {
    ql = max(ql, 0);
    return query(ql, qr, LO, HI, 0);
  }
};
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int n, lo, hi;
  cin >> n >> lo >> hi;
  vector<int> arr(n + 1);
  for (int i = 1; i <= n; i++) cin >> arr[i];
  sort(arr.begin(), arr.end());
  vector<int> dp(n + 1);
  const int INF = 1e9;
  SegmentTree seg_dp(n + 1), seg_val(n + 1);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  auto add = [&](int where) {
    if (where == n) return;
    const int A = dp[where];
    const int B = arr[where + 1];
    const int CHANGE = B + A + 1;
    seg_dp.modify(where, A);
    pq.push({CHANGE, where});
  };
  auto update = [&](int delta) {
    while(!pq.empty()) {
      int cur = pq.top().first;
      if (cur > delta) break;
      int where = pq.top().second;
      pq.pop();
      seg_dp.modify(where, INF);
      seg_val.modify(where, delta - arr[where + 1]); 
    }
  };
  for (int i = 0; i <= n; i++) dp[i] = INF;
  dp[0] = 0;
  add(0);
  for (int i = 1; i <= n; i++) {
    if (i > 1) {
      const int D = arr[i] - arr[i - 1];
      seg_val.range_update(0, i - 1, +D);
    }
    update(arr[i]);
    if (i >= lo){
      dp[i] = min(seg_dp.query(i - hi, i - lo), seg_val.query(i - hi, i - lo));
      add(i);
    }
  }
  cout << dp[n] << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 129 ms 8532 KB Output is correct
3 Correct 13 ms 1152 KB Output is correct
4 Correct 1746 ms 79304 KB Output is correct
5 Correct 1583 ms 79160 KB Output is correct
6 Correct 200 ms 8564 KB Output is correct
7 Correct 1400 ms 72036 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 129 ms 8532 KB Output is correct
3 Correct 13 ms 1152 KB Output is correct
4 Correct 1746 ms 79304 KB Output is correct
5 Correct 1583 ms 79160 KB Output is correct
6 Correct 200 ms 8564 KB Output is correct
7 Correct 1400 ms 72036 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 50 ms 2560 KB Output is correct
12 Correct 83 ms 4096 KB Output is correct
13 Correct 128 ms 5248 KB Output is correct
14 Correct 148 ms 6016 KB Output is correct
15 Correct 1473 ms 50872 KB Output is correct
16 Correct 1776 ms 56824 KB Output is correct
17 Correct 151 ms 6016 KB Output is correct
18 Correct 135 ms 5368 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Execution timed out 2078 ms 70740 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 129 ms 8532 KB Output is correct
3 Correct 13 ms 1152 KB Output is correct
4 Correct 1746 ms 79304 KB Output is correct
5 Correct 1583 ms 79160 KB Output is correct
6 Correct 200 ms 8564 KB Output is correct
7 Correct 1400 ms 72036 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 50 ms 2560 KB Output is correct
12 Correct 83 ms 4096 KB Output is correct
13 Correct 128 ms 5248 KB Output is correct
14 Correct 148 ms 6016 KB Output is correct
15 Correct 1473 ms 50872 KB Output is correct
16 Correct 1776 ms 56824 KB Output is correct
17 Correct 151 ms 6016 KB Output is correct
18 Correct 135 ms 5368 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Execution timed out 2078 ms 70740 KB Time limit exceeded
21 Halted 0 ms 0 KB -