fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #ifdef DEBUG
  4. #define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
  5. #else
  6. #define eprintf(...) ;
  7. #endif
  8.  
  9. const int inf = (int) 1e9 + 100;
  10.  
  11. //стек с минимумом за неамортизированное O(1)
  12. class Vector {
  13.   int *a, *b;
  14.   int *a_min, *b_min;
  15.   int pos; // vector[i] == ((i < pos) ? a[i] : b[i]);
  16.   int n; //number of elements in our vector
  17.   int mem; //size of b
  18.  
  19.   public:
  20.  
  21.   Vector() {
  22.     a = a_min = nullptr;
  23.     b = new int[1];
  24.     b_min = new int[1];
  25.     mem = 1;
  26.     n = 0;
  27.     pos = 0;
  28.   }
  29.  
  30.   //оператор= должен копировать данные
  31.   //работает за O(n)
  32.   Vector& operator=(const Vector & other) {
  33.     if (this != &other) {
  34.       pos = other.pos;
  35.       n = other.n;
  36.       mem = other.mem;
  37.       a = new int[mem / 2];
  38.       a_min = new int[mem / 2];
  39.       for (int i = 0; i < mem / 2; i++) {
  40.         a[i] = other.a[i];
  41.         a_min[i] = other.a_min[i];
  42.       }
  43.       b = new int[mem];
  44.       b_min = new int[mem];
  45.       for (int i = 0; i < mem; i++) {
  46.         b[i] = other.b[i];
  47.         b_min[i] = other.b_min[i];
  48.       }
  49.     }
  50.     return *this;
  51.   }
  52.  
  53.   //быстрый swap за O(1)
  54.   void swap(Vector & other) {
  55.     std::swap(pos, other.pos);
  56.     std::swap(n, other.n);
  57.     std::swap(mem, other.mem);
  58.     std::swap(a, other.a);
  59.     std::swap(a_min, other.a_min);
  60.     std::swap(b, other.b);
  61.     std::swap(b_min, other.b_min);
  62.   }
  63.  
  64.   //нужно, чтобы память не утекала
  65.   ~Vector() {
  66.     delete [] a;
  67.     delete [] a_min;
  68.     delete [] b;
  69.     delete [] b_min;
  70.   }
  71.  
  72.   int size() const {
  73.     return n;
  74.   }
  75.  
  76.   void copy() {
  77.     if (pos > 0) {
  78.       pos--;
  79.       b[pos] = a[pos];
  80.       b_min[pos] = a_min[pos];
  81.     }
  82.   }
  83.  
  84.   void push_back(int x) {
  85.     copy();
  86.     if (n == mem) {
  87.       delete [] a;
  88.       delete [] a_min;
  89.       a = b;
  90.       a_min = b_min;
  91.       mem *= 2;
  92.       pos = n;
  93.       b = new int[mem];
  94.       b_min = new int[mem];
  95.     }
  96.     b[n++] = x;
  97.     b_min[n - 1] = x;
  98.     if (n > 1) {
  99.       if (n - 2 >= pos) {
  100.         b_min[n - 1] = std::min(b_min[n - 2], b[n - 1]);
  101.       } else {
  102.         b_min[n - 1] = std::min(a_min[n - 2], b[n - 1]);
  103.       }
  104.     }
  105.   }
  106.  
  107.   int operator[](int i) const {
  108.     if (i < pos) {
  109.       return a[i];
  110.     } else {
  111.       return b[i];
  112.     }
  113.   }
  114.  
  115.   int get_min() const {
  116.     if (n == 0) {
  117.       return inf;
  118.     }
  119.     return (n - 1 >= pos) ? b_min[n - 1] : a_min[n - 1];
  120.   }
  121.  
  122.   int back() const {
  123.     assert(n > 0);
  124.     return (*this)[n - 1];
  125.   }
  126.  
  127.   int pop_back() {
  128.     assert(n > 0);
  129.     return (*this)[--n];
  130.   }
  131.  
  132.   void print() const {
  133.     for (int i = 0; i < size(); i++) {
  134.       std::printf("%d ", (*this)[i]);
  135.     }
  136.     std::printf("\n");
  137.   }
  138. };
  139.  
  140. //очередь с минимумом за неамортизированное O(1)
  141. class Queue {
  142.   Vector a, b, a1, b1;
  143.  
  144.   int len;
  145.  
  146.   public:
  147.  
  148.   Queue() {
  149.     len = 0;
  150.   }
  151.  
  152.   int size() {
  153.     return len;
  154.   }
  155.  
  156.   int get_min() {
  157.     int res = inf;
  158.     res = std::min(res, a.get_min());
  159.     res = std::min(res, b.get_min());
  160.     res = std::min(res, b1.get_min());
  161.     return res;
  162.   }
  163.  
  164.   void change() {
  165.     if (a1.size() == a.size() + b.size()) {
  166.       a.swap(a1);
  167.       b.swap(b1);
  168.       a1 = Vector();
  169.       b1 = Vector();
  170.     }
  171.   }
  172.  
  173.   void step() {
  174.     change();
  175.     assert(a1.size() < a.size() + b.size());
  176.     if (a1.size() < b.size()) {
  177.       a1.push_back(b[b.size() - a1.size() - 1]);
  178.     } else {
  179.       a1.push_back(a[a1.size() - b.size()]);
  180.     }
  181.     change();
  182.     assert(a1.size() < a.size() + b.size()); //нужно, для того чтобы pop работал, как было замечено на лекции
  183.   }
  184.  
  185.   void push(int x) {
  186.     b1.push_back(x);
  187.     len++;
  188.     step(); //сохраняем инвариант a1.size() >= b1.size()
  189.   }
  190.  
  191.   int pop() {
  192.     assert(len >= 1);
  193.     step(); //a не пуст, a1.size() < a.size() + b.size()
  194.     len--;
  195.     int res = a.pop_back();
  196.     return res;
  197.   }
  198. };
  199.  
  200. void solve() {
  201.   Queue q;
  202.   q.push(10);
  203.   printf("%d\n", q.get_min());
  204.   q.push(5);
  205.   printf("%d\n", q.get_min());
  206.   q.push(7);
  207.   printf("%d\n", q.get_min());
  208.   q.pop();
  209.   printf("%d\n", q.get_min());
  210.   q.pop();
  211.   printf("%d\n", q.get_min());
  212.   q.push(3);
  213.   printf("%d\n", q.get_min());
  214.   q.push(8);
  215.   printf("%d\n", q.get_min());
  216.   q.pop();
  217.   printf("%d\n", q.get_min());
  218.   q.pop();
  219.   printf("%d\n", q.get_min());
  220.   q.pop();
  221.   printf("%d\n", q.get_min());
  222. }
  223.  
  224. int main() {
  225.   solve();
  226.   return 0;
  227. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
5
5
5
7
3
3
3
8
1000000100
https://ideone.com/jFAJsp
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!