oj.uz

Submission #263207

# Submission time Handle Problem Language Result Execution time Memory
263207 2020-08-13T14:05:23 Z Haunted_Cpp Swimming competition (LMIO18_plaukimo_varzybos) C++11
30 / 100
 2000 ms 110112 KB 
#include <bits/stdc++.h>

static struct FASTIO {

  char READ_CHARACTER; bool REMAINING_CHARACTER = false;

  inline void ignore(); inline void flush();

  template <typename T> inline bool READ_INT(T &x); template <typename T> inline bool READ_STRING(T &x);
  /*                                                          Fast I/O Code Optimizer                                                          */
  template<size_t N> inline bool READ_CHAR_ARRAY(char (&x)[N]); template<size_t N> inline bool READ_VAR(char (&x)[N]);
  /*                    A tool to optimize execution time of C++ codes by replacing methods of reading and writing variables                   */
  template <typename T> inline bool READ_CHAR(T &x); inline bool READ_CHAR_ARRAY(char*& x); inline bool READ_GETLINE(std::string &x);
  /*                                                    Use it on fastio.pythonanywhere.com                                                    */
  template <typename T> inline bool READ_FLOAT(T &x); template <typename T> inline bool READ_DOUBLE(T &x);
  /*                                          Github Project: github.com/bfs07/Fast-IO-Code-Optimizer                                          */
  template<std::size_t N> inline bool READ_BITSET(std::bitset<N> &bit); template<std::size_t N> inline bool READ_VAR(std::bitset<N> &bit);
  inline bool READ_VAR(bool &x); inline bool READ_VAR(short int &x); inline bool READ_VAR(int &x); 
  inline bool READ_VAR(long int &x); inline bool READ_VAR(long long int &x); inline bool READ_VAR(unsigned short int &x);
  inline bool READ_VAR(unsigned int &x); inline bool READ_VAR(unsigned long &x); inline bool READ_VAR(unsigned long long &x);
  inline bool READ_VAR(std::string &x); inline bool READ_VAR(char &x); inline bool READ_VAR(char*& x); inline bool READ_VAR(float &x);
  inline bool READ_VAR(double &x); inline bool READ_VAR(long double &x); template <typename T> inline void WRITE_INT(T x);
  inline void WRITE_STRING(std::string &x); inline void WRITE_CHAR(char x); inline void WRITE_CHAR_ARRAY(const char *x);
  inline void WRITE_FLOAT(float x); template <typename T> inline void WRITE_DOUBLE(T x); inline void WRITE_VAR(bool x);
  inline void WRITE_VAR(short int x); inline void WRITE_VAR(int x); inline void WRITE_VAR(long int x); inline void WRITE_VAR(long long int x);
  inline void WRITE_VAR(unsigned short int x); inline void WRITE_VAR(unsigned int x); inline void WRITE_VAR(unsigned long x);
  inline void WRITE_VAR(unsigned long long x); inline void WRITE_VAR(char x); inline void WRITE_VAR(const char *x); 
  inline void WRITE_VAR(std::string &x); inline void WRITE_VAR(float x); inline void WRITE_VAR(double x); inline void WRITE_VAR(long double x);
  template<std::size_t N> inline void WRITE_VAR(std::bitset<N> &bit); template<std::size_t N> inline void WRITE_BITSET(std::bitset<N> &bit);

} __FIO__;


 
 
#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 () {
  0;
  0; 
  int n, lo, hi;
  __FIO__.READ_VAR(n), __FIO__.READ_VAR(lo), __FIO__.READ_VAR(hi);
  vector<int> arr(n + 1);
  for (int i = 1; i <= n; i++) __FIO__.READ_VAR(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);
   
  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);
     
  };
  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);
    }
  }
  __FIO__.WRITE_VAR(dp[n]), __FIO__.WRITE_VAR('\n');
  return 0;
}


#undef debug
#undef debug
#undef debug
#undef debug

inline void FASTIO::ignore() {
  if(REMAINING_CHARACTER == true) REMAINING_CHARACTER = false; else READ_CHARACTER = getchar();
}

inline void FASTIO::flush() {
  fflush(stdout);
}

// cin modifications

template <typename T>
inline bool FASTIO::READ_INT(T &x) {
  x = 0; T sig = 1;
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while (!isdigit(READ_CHARACTER) && READ_CHARACTER != EOF) sig = (READ_CHARACTER == '-' ? -sig : sig), READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while (isdigit(READ_CHARACTER)) x = x * 10 + READ_CHARACTER - '0', READ_CHARACTER = getchar();
  x *= sig; REMAINING_CHARACTER = true;
  return true;
}

template <typename T>
inline bool FASTIO::READ_STRING(T &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_GETLINE(std::string &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = false;
  return true;
}

template <typename T>
inline bool FASTIO::READ_CHAR(T &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  x = READ_CHARACTER; REMAINING_CHARACTER = false;
  return true;
}


template<size_t N>
inline bool FASTIO::READ_CHAR_ARRAY(char (&x)[N]) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  char *ptr = &x[0];
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) *ptr++ = READ_CHARACTER, READ_CHARACTER = getchar();
  *ptr = '\0', REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_CHAR_ARRAY(char*& x) {
  std::string y;
  if(READ_STRING(y) == false)
    return false;
  x = new char[(int)y.size() + 1];
  strcpy(x, y.c_str());
  return true;
}

template <typename T>
inline bool FASTIO::READ_FLOAT(T &x) {
  return (scanf("%f", &x) != EOF);
}

template <typename T>
inline bool FASTIO::READ_DOUBLE(T &x) {
  double y;
  if(scanf("%lf", &y) == EOF) return false;
  x = y;
  return true;
}

template<std::size_t N>
inline bool FASTIO::READ_BITSET(std::bitset<N> &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  int i = 0; REMAINING_CHARACTER = true;
  while (READ_CHARACTER == '0' || READ_CHARACTER == '1') x[i++] = READ_CHARACTER - '0', READ_CHARACTER = getchar();
  return true;
}

inline bool FASTIO::READ_VAR(short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(std::string &x) {
  return READ_STRING(x);    
}

inline bool FASTIO::READ_VAR(char &x) {
  return READ_CHAR(x);
}

template<size_t N>
inline bool FASTIO::READ_VAR(char (&x)[N]) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(char*& x) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(float &x) {
  return READ_FLOAT(x);
}

inline bool FASTIO::READ_VAR(double &x) {
  return READ_DOUBLE(x);
}

inline bool FASTIO::READ_VAR(long double &x) {
  return READ_DOUBLE(x);
}

template<std::size_t N>
inline bool FASTIO::READ_VAR(std::bitset<N> &x) {
  return READ_BITSET(x);
}

// cout modifications

template <typename T>
inline void FASTIO::WRITE_INT(T x) {
  if (x < 0) {putchar('-'); x = -x; }
  char writeBuffer[20], *writePtr = writeBuffer;
  do {
    *writePtr++ = '0' + x % 10;
    x /= 10;
  }
  while (x);
  do  { putchar(*--writePtr); }
  while (writePtr > writeBuffer);
}

inline void FASTIO::WRITE_CHAR(char x) {
  putchar(x);
}

inline void FASTIO::WRITE_CHAR_ARRAY(const char *x) {
  while(*x != '\0')
    putchar(*x++);
}

inline void FASTIO::WRITE_STRING(std::string &x) {
  for(char c: x) 
    putchar(c);
}

inline void FASTIO::WRITE_FLOAT(float x) {
  printf("%f", x);
}

template <typename T>
inline void FASTIO::WRITE_DOUBLE(T x) {
  printf("%lf", (double)x);
}

template<std::size_t N>
inline void FASTIO::WRITE_BITSET(std::bitset<N> &x) {
  for(int i = (int)x.size() - 1; i >= 0; i--)
    putchar(x[i] + 48);
}

inline void FASTIO::WRITE_VAR(bool x) {
  WRITE_INT(x);
}

inline void FASTIO::WRITE_VAR(short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(std::string &x) {
  WRITE_STRING(x);    
}

inline void FASTIO::WRITE_VAR(char x) {
  WRITE_CHAR(x);
}

inline void FASTIO::WRITE_VAR(const char *x) {
  WRITE_CHAR_ARRAY(x);
}

inline void FASTIO::WRITE_VAR(float x) {
  WRITE_FLOAT(x);
}

inline void FASTIO::WRITE_VAR(double x) {
  WRITE_DOUBLE(x);
}

inline void FASTIO::WRITE_VAR(long double x) {
  WRITE_DOUBLE(x);
}

template<std::size_t N>
inline void FASTIO::WRITE_VAR(std::bitset<N> &x) {
  WRITE_BITSET(x);
}

Compilation message

plaukimo_varzybos.cpp: In function 'int main()':
plaukimo_varzybos.cpp:131:3: warning: statement has no effect [-Wunused-value]
  131 |   0;
      |   ^
plaukimo_varzybos.cpp:132:3: warning: statement has no effect [-Wunused-value]
  132 |   0;
      |   ^
plaukimo_varzybos.cpp: In instantiation of 'void FASTIO::WRITE_INT(T) [with T = bool]':
plaukimo_varzybos.cpp:390:14:   required from here
plaukimo_varzybos.cpp:349:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
  349 |   if (x < 0) {putchar('-'); x = -x; }
      |       ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23808 KB Output is correct
2 Correct 109 ms 30848 KB Output is correct
3 Correct 35 ms 24576 KB Output is correct
4 Correct 1487 ms 102008 KB Output is correct
5 Correct 1200 ms 94328 KB Output is correct
6 Correct 148 ms 31864 KB Output is correct
7 Correct 1073 ms 87668 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 23 ms 23808 KB Output is correct
3 Correct 25 ms 23808 KB Output is correct
4 Correct 17 ms 23808 KB Output is correct
5 Correct 16 ms 23936 KB Output is correct
6 Correct 16 ms 23808 KB Output is correct
7 Correct 23 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 24 ms 23808 KB Output is correct
10 Correct 19 ms 23936 KB Output is correct
11 Correct 26 ms 23936 KB Output is correct
12 Correct 25 ms 23808 KB Output is correct
13 Correct 16 ms 23856 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 109 ms 30848 KB Output is correct
3 Correct 35 ms 24576 KB Output is correct
4 Correct 1487 ms 102008 KB Output is correct
5 Correct 1200 ms 94328 KB Output is correct
6 Correct 148 ms 31864 KB Output is correct
7 Correct 1073 ms 87668 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 64 ms 26616 KB Output is correct
12 Correct 93 ms 27512 KB Output is correct
13 Correct 134 ms 29200 KB Output is correct
14 Correct 174 ms 31876 KB Output is correct
15 Correct 1360 ms 76144 KB Output is correct
16 Correct 1857 ms 97400 KB Output is correct
17 Correct 182 ms 31892 KB Output is correct
18 Correct 135 ms 29176 KB Output is correct
19 Correct 16 ms 23808 KB Output is correct
20 Execution timed out 2093 ms 110112 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 109 ms 30848 KB Output is correct
3 Correct 35 ms 24576 KB Output is correct
4 Correct 1487 ms 102008 KB Output is correct
5 Correct 1200 ms 94328 KB Output is correct
6 Correct 148 ms 31864 KB Output is correct
7 Correct 1073 ms 87668 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 64 ms 26616 KB Output is correct
12 Correct 93 ms 27512 KB Output is correct
13 Correct 134 ms 29200 KB Output is correct
14 Correct 174 ms 31876 KB Output is correct
15 Correct 1360 ms 76144 KB Output is correct
16 Correct 1857 ms 97400 KB Output is correct
17 Correct 182 ms 31892 KB Output is correct
18 Correct 135 ms 29176 KB Output is correct
19 Correct 16 ms 23808 KB Output is correct
20 Execution timed out 2093 ms 110112 KB Time limit exceeded
21 Halted 0 ms 0 KB -