oj.uz

Submission #263195

# Submission time Handle Problem Language Result Execution time Memory
263195 2020-08-13T13:59:12 Z Haunted_Cpp Swimming competition (LMIO18_plaukimo_varzybos) C++17
30 / 100
 2000 ms 133864 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);
  }
};

vector<vector<int>> g(2000005);
 
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);
    g[CHANGE].emplace_back(where);
    //~ pq.push({CHANGE, where});
  };
  int last_one = 0;
  auto update = [&](int delta) {
    //~ if (delta <=
    //~ assert(delta <= 1000000);
    while(last_one <= delta) {
      for (auto where : g[last_one]) {
        //~ int cur = last_one;
        seg_dp.modify(where, INF);
        seg_val.modify(where, delta - arr[where + 1]); 
        //~ int where = 
      }
      //~ int cur = pq.top().first;
      //~ if (cur > delta) break;
      //~ int where = pq.top().second;
      //~ pq.pop();
      
      ++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 39 ms 47352 KB Output is correct
2 Correct 130 ms 54520 KB Output is correct
3 Correct 50 ms 48120 KB Output is correct
4 Correct 1497 ms 125524 KB Output is correct
5 Correct 1227 ms 117956 KB Output is correct
6 Correct 167 ms 55416 KB Output is correct
7 Correct 1090 ms 110852 KB Output is correct
8 Correct 38 ms 47360 KB Output is correct
9 Correct 38 ms 47344 KB Output is correct
10 Correct 39 ms 47352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47360 KB Output is correct
2 Correct 38 ms 47344 KB Output is correct
3 Correct 39 ms 47352 KB Output is correct
4 Correct 32 ms 47336 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 31 ms 47264 KB Output is correct
7 Correct 40 ms 47352 KB Output is correct
8 Correct 34 ms 47224 KB Output is correct
9 Correct 38 ms 47360 KB Output is correct
10 Correct 37 ms 47352 KB Output is correct
11 Correct 38 ms 47352 KB Output is correct
12 Correct 39 ms 47360 KB Output is correct
13 Correct 32 ms 47360 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct
2 Correct 130 ms 54520 KB Output is correct
3 Correct 50 ms 48120 KB Output is correct
4 Correct 1497 ms 125524 KB Output is correct
5 Correct 1227 ms 117956 KB Output is correct
6 Correct 167 ms 55416 KB Output is correct
7 Correct 1090 ms 110852 KB Output is correct
8 Correct 38 ms 47360 KB Output is correct
9 Correct 38 ms 47344 KB Output is correct
10 Correct 39 ms 47352 KB Output is correct
11 Correct 84 ms 50168 KB Output is correct
12 Correct 106 ms 51068 KB Output is correct
13 Correct 149 ms 52600 KB Output is correct
14 Correct 195 ms 55416 KB Output is correct
15 Correct 1391 ms 99692 KB Output is correct
16 Correct 1913 ms 121044 KB Output is correct
17 Correct 197 ms 55288 KB Output is correct
18 Correct 166 ms 52600 KB Output is correct
19 Correct 34 ms 47360 KB Output is correct
20 Execution timed out 2102 ms 133864 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct
2 Correct 130 ms 54520 KB Output is correct
3 Correct 50 ms 48120 KB Output is correct
4 Correct 1497 ms 125524 KB Output is correct
5 Correct 1227 ms 117956 KB Output is correct
6 Correct 167 ms 55416 KB Output is correct
7 Correct 1090 ms 110852 KB Output is correct
8 Correct 38 ms 47360 KB Output is correct
9 Correct 38 ms 47344 KB Output is correct
10 Correct 39 ms 47352 KB Output is correct
11 Correct 84 ms 50168 KB Output is correct
12 Correct 106 ms 51068 KB Output is correct
13 Correct 149 ms 52600 KB Output is correct
14 Correct 195 ms 55416 KB Output is correct
15 Correct 1391 ms 99692 KB Output is correct
16 Correct 1913 ms 121044 KB Output is correct
17 Correct 197 ms 55288 KB Output is correct
18 Correct 166 ms 52600 KB Output is correct
19 Correct 34 ms 47360 KB Output is correct
20 Execution timed out 2102 ms 133864 KB Time limit exceeded
21 Halted 0 ms 0 KB -