fork(5) download
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. int main(){
  9. unsigned n; scanf("%u", &n);
  10. ll a, b, c, x, sum = 0;
  11. scanf("%lld %lld %lld %lld", &a, &b, &c, &x);
  12.  
  13. unsigned capacity = unsigned(1e6);
  14. ll *head = (ll*)calloc(capacity + 1, sizeof(ll)); //стек, из которого удаляют элементы
  15. ll *hmin = (ll*)calloc(capacity + 1, sizeof(ll)); //его локальные минимумы
  16. ll *tail = (ll*)calloc(capacity + 1, sizeof(ll)); //стек, в который добавляют элементы
  17. ll *tmin = (ll*)calloc(capacity + 1, sizeof(ll)); //его локальные минимумы
  18. ll r = 0, l = 0; //позиции в первом и втором стеках
  19.  
  20. while(n--){
  21. x = (a*x*x + b*x + c)/100 % 1000000; //подсчет нового значения Х
  22. if(x % 5 < 2){
  23. if(l == 0){ //если голова пуста
  24. hmin[1] = head[1] = tail[r]; //инициализация головы очереди
  25. for(l = 2; l <= r; l++){ //переносим элементы из первого стека во второй, из хвоста в очередь (в обратном порядке)
  26. head[l] = tail[r - l + 1]; //реализация обратного порядка обхода
  27. hmin[l] = min(hmin[l-1], head[l]); //минимум на данном шаге равен минимуму из предыдущего и текущего
  28. }
  29. r = 0; //хвост очереди очищен
  30. l--; //голова перезаписана
  31. }
  32. l--; //сдвиг влево на текущую позицию
  33. }
  34. else{
  35. tail[++r] = x; //записать x в хвост
  36. if(r == 1) //если очередь состоит из одного элемента
  37. tmin[r] = x; //то он же и является минимальным
  38. else
  39. tmin[r] = min(tmin[r-1], x); //иначе оптимальный элемент равен минимуму из того, что было, и нового элемента
  40. }
  41. if(r > 0 && l > 0) //если и голова, и хвост непусты
  42. sum += min(tmin[r], hmin[l]); //то добавить к сумме минимум из значений в голове и хвосте
  43. else
  44. if(r > 0 && l == 0)
  45. sum += tmin[r];
  46. else
  47. if(r == 0 && l>0)
  48. sum += hmin[l];
  49. }
  50. printf("%lld\n", sum);
  51. return 0;
  52. }
  53.  
Time limit exceeded #stdin #stdout 5s 34408KB
stdin
Standard input is empty
stdout
Standard output is empty