fork download
copy 
  1. // FR_14_09 - Przeciążenia procesora.cpp : This file contains the 'main' function. Program execution begins and ends there.
  2. //
  3.  
  4. #include <iostream>
  5.  
  6. #include <map>
  7. #include <list>
  8. #include <string>
  9. #include <vector>
  10. #include <deque>
  11.  
  12. using namespace std;
  13.  
  14. map<int, int, std::greater<int>> mOdczytCounts;
  15. int* lOdczyts;
  16.  
  17. deque<pair<int, int>> dOdczyts;
  18.  
  19. inline void appendInt(std::string& out, int value) 
  20. {
  21.     static char buf[11]; // wystarczy dla 32-bit unsigned int (max 10 cyfr) + '\n'
  22.     char* p = buf + sizeof(buf);
  23.  
  24.     *--p = '\n';
  25.  
  26.     do {
  27.         *--p = '0' + (value % 10);
  28.         value /= 10;
  29.     } while (value != 0);
  30.  
  31.     out.append(p, buf + sizeof(buf) - p);
  32. }
  33.  
  34. void removeOldestSmallerOrEqualThan(deque<pair<int, int>>& col, int value)
  35. {
  36.     while (col.size() && col.front().second <= value)
  37.         col.pop_front();
  38. }
  39.  
  40. void removeOldest(deque<pair<int, int>>& col, int index)
  41. {
  42.     while (col.size() && col.front().first <= index)
  43.         col.pop_front();
  44. }
  45.  
  46. int mainDeque()
  47. {
  48.     int nSize;
  49.     //int odczyt;
  50.  
  51.     std::ios::sync_with_stdio(false);
  52.  
  53.     string strOut;
  54.     cin >> nSize;
  55.  
  56.     int index = 0;
  57.     int value;
  58.     int size = nSize;
  59.  
  60.     while (nSize--)
  61.     {
  62.         std::cin >> value;
  63.  
  64.         removeOldestSmallerOrEqualThan(dOdczyts, value);
  65.  
  66.         dOdczyts.push_back({ index++, value });
  67.     }
  68.  
  69.  
  70.     while (std::cin >> value)
  71.     {
  72.         appendInt(strOut, dOdczyts.begin()->second);
  73.  
  74.         removeOldestSmallerOrEqualThan(dOdczyts, value);
  75.         removeOldest(dOdczyts, index - size);
  76.  
  77.         dOdczyts.push_back({ index++, value });
  78.     }
  79.  
  80.     appendInt(strOut, dOdczyts.begin()->second);
  81.  
  82.     std::cout << strOut;
  83.     return 0;
  84. }
  85.  
  86. int mainMapa()
  87. {
  88.     int nSize;
  89.     //int odczyt;
  90.  
  91.     std::ios::sync_with_stdio(false);
  92.  
  93.     string strOut;
  94.     cin >> nSize;
  95.  
  96.     //list<int>::iterator listIt;
  97.  
  98.     lOdczyts = new int[1000000];
  99.     int* pOdczyt = lOdczyts;
  100.  
  101.     while (--nSize)
  102.     {
  103.         std::cin >> *pOdczyt;
  104.  
  105.         ++mOdczytCounts[*pOdczyt++];
  106.     }
  107.  
  108.     strOut.reserve(10000000);
  109.     int* listIt = lOdczyts;
  110.     //char buf[16]; // wystarczy dla int (nawet z minusem i '\0')
  111.  
  112.     while (std::cin >> *pOdczyt)
  113.     {
  114.         ++mOdczytCounts[*pOdczyt++];
  115.  
  116.         //strOut += std::to_string(mOdczytCounts.begin()->first);
  117.         //strOut += '\n';
  118.  
  119.         //int len = std::snprintf(buf, sizeof(buf), "%d", mOdczytCounts.begin()->first);
  120.         appendInt(strOut, mOdczytCounts.begin()->first);
  121.         //strOut += '\n';
  122.  
  123.         auto it = mOdczytCounts.find(*listIt);
  124.         it->second--;
  125.  
  126.         ++listIt;
  127.  
  128.         if (it->second == 0) mOdczytCounts.erase(it);
  129.     }
  130.  
  131.     std::cout << strOut;
  132.     return 0;
  133. }
  134.  
  135. int main()
  136. {
  137.     return mainDeque();
  138. }
  139.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
5 2 3 4 3 7 4 5
stdout
copy 
5
7
7
7
https://ideone.com/t6sxhQ
language:
C++ (gcc 8.3)
created:
15 hours 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!