oj.uz

Submission #263198

# Submission time Handle Problem Language Result Execution time Memory
263198 2020-08-13T14:00:30 Z Haunted_Cpp Swimming competition (LMIO18_plaukimo_varzybos) C++17
30 / 100
 2000 ms 110628 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 = 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));
      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 29 ms 23800 KB Output is correct
2 Correct 125 ms 30824 KB Output is correct
3 Correct 36 ms 24704 KB Output is correct
4 Correct 1491 ms 102144 KB Output is correct
5 Correct 1197 ms 94488 KB Output is correct
6 Correct 147 ms 32024 KB Output is correct
7 Correct 1106 ms 87560 KB Output is correct
8 Correct 23 ms 23808 KB Output is correct
9 Correct 23 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 23 ms 23808 KB Output is correct
2 Correct 23 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 17 ms 23808 KB Output is correct
6 Correct 16 ms 23808 KB Output is correct
7 Correct 23 ms 23808 KB Output is correct
8 Correct 17 ms 23808 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 25 ms 23808 KB Output is correct
12 Correct 26 ms 23808 KB Output is correct
13 Correct 16 ms 23808 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 125 ms 30824 KB Output is correct
3 Correct 36 ms 24704 KB Output is correct
4 Correct 1491 ms 102144 KB Output is correct
5 Correct 1197 ms 94488 KB Output is correct
6 Correct 147 ms 32024 KB Output is correct
7 Correct 1106 ms 87560 KB Output is correct
8 Correct 23 ms 23808 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 23 ms 23808 KB Output is correct
11 Correct 65 ms 26680 KB Output is correct
12 Correct 96 ms 27640 KB Output is correct
13 Correct 144 ms 29196 KB Output is correct
14 Correct 183 ms 31864 KB Output is correct
15 Correct 1418 ms 76196 KB Output is correct
16 Correct 1932 ms 97576 KB Output is correct
17 Correct 179 ms 31864 KB Output is correct
18 Correct 142 ms 29108 KB Output is correct
19 Correct 19 ms 23808 KB Output is correct
20 Execution timed out 2101 ms 110628 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 125 ms 30824 KB Output is correct
3 Correct 36 ms 24704 KB Output is correct
4 Correct 1491 ms 102144 KB Output is correct
5 Correct 1197 ms 94488 KB Output is correct
6 Correct 147 ms 32024 KB Output is correct
7 Correct 1106 ms 87560 KB Output is correct
8 Correct 23 ms 23808 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 23 ms 23808 KB Output is correct
11 Correct 65 ms 26680 KB Output is correct
12 Correct 96 ms 27640 KB Output is correct
13 Correct 144 ms 29196 KB Output is correct
14 Correct 183 ms 31864 KB Output is correct
15 Correct 1418 ms 76196 KB Output is correct
16 Correct 1932 ms 97576 KB Output is correct
17 Correct 179 ms 31864 KB Output is correct
18 Correct 142 ms 29108 KB Output is correct
19 Correct 19 ms 23808 KB Output is correct
20 Execution timed out 2101 ms 110628 KB Time limit exceeded
21 Halted 0 ms 0 KB -