oj.uz

Submission #263215

# Submission time Handle Problem Language Result Execution time Memory
263215 2020-08-13T14:08:49 Z Haunted_Cpp Swimming competition (LMIO18_plaukimo_varzybos) C++11
30 / 100
 2000 ms 111680 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);
  }
};

const int MAX_N = 1e6 + 5;
vector<vector<int>> g(MAX_N);
 
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);
    if (CHANGE < MAX_N) g[CHANGE].emplace_back(where);
    //~ pq.push({CHANGE, where});
  };
  int last_one = 0;
  auto update = [&](int delta) {
    while(last_one <= delta) {
      for (auto where : g[last_one]) {
        seg_dp.modify(where, INF);
        seg_val.modify(where, delta - arr[where + 1]); 
      }
      ++last_one;
    }
  };
  for (int i = 0; i <= n; i++) dp[i] = INF;
  dp[0] = 0;
  add(0);
  for (int i = 2; i < lo; i++) {
    const int D = arr[i] - arr[i - 1];
    seg_val.range_update(0, i - 1, +D);
    update(arr[i]);
  }
  for (int i = lo; i <= n; i++) {
    const int D = arr[i] - arr[i - 1];
    seg_val.range_update(0, i - 1, +D);
    update(arr[i]);
    dp[i] = min(seg_dp.query(i - hi, i - lo), seg_val.query(i - hi, i - lo));
    if (dp[i] < INF) add(i);
  }
  cout << dp[n] << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23808 KB Output is correct
2 Correct 101 ms 30848 KB Output is correct
3 Correct 33 ms 24576 KB Output is correct
4 Correct 1431 ms 102072 KB Output is correct
5 Correct 1149 ms 94612 KB Output is correct
6 Correct 149 ms 31864 KB Output is correct
7 Correct 1000 ms 87560 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 23 ms 23808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 21 ms 23808 KB Output is correct
3 Correct 23 ms 23808 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Correct 21 ms 23808 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct
9 Correct 22 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 25 ms 23808 KB Output is correct
12 Correct 23 ms 23808 KB Output is correct
13 Correct 15 ms 23808 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23808 KB Output is correct
2 Correct 101 ms 30848 KB Output is correct
3 Correct 33 ms 24576 KB Output is correct
4 Correct 1431 ms 102072 KB Output is correct
5 Correct 1149 ms 94612 KB Output is correct
6 Correct 149 ms 31864 KB Output is correct
7 Correct 1000 ms 87560 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 23 ms 23808 KB Output is correct
11 Correct 62 ms 26744 KB Output is correct
12 Correct 87 ms 27640 KB Output is correct
13 Correct 128 ms 29292 KB Output is correct
14 Correct 170 ms 31996 KB Output is correct
15 Correct 1369 ms 76420 KB Output is correct
16 Correct 1800 ms 97656 KB Output is correct
17 Correct 182 ms 31868 KB Output is correct
18 Correct 129 ms 29176 KB Output is correct
19 Correct 15 ms 23808 KB Output is correct
20 Execution timed out 2088 ms 111680 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23808 KB Output is correct
2 Correct 101 ms 30848 KB Output is correct
3 Correct 33 ms 24576 KB Output is correct
4 Correct 1431 ms 102072 KB Output is correct
5 Correct 1149 ms 94612 KB Output is correct
6 Correct 149 ms 31864 KB Output is correct
7 Correct 1000 ms 87560 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 23 ms 23808 KB Output is correct
11 Correct 62 ms 26744 KB Output is correct
12 Correct 87 ms 27640 KB Output is correct
13 Correct 128 ms 29292 KB Output is correct
14 Correct 170 ms 31996 KB Output is correct
15 Correct 1369 ms 76420 KB Output is correct
16 Correct 1800 ms 97656 KB Output is correct
17 Correct 182 ms 31868 KB Output is correct
18 Correct 129 ms 29176 KB Output is correct
19 Correct 15 ms 23808 KB Output is correct
20 Execution timed out 2088 ms 111680 KB Time limit exceeded
21 Halted 0 ms 0 KB -