fork download 
  1. /* USE AT YOUR OWN RISK */
  2. /* Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn */
  3.  
  4. #include <cmath>
  5. #include <ctime>
  6. #include <cstdio>
  7. #include <cassert>
  8. #include <climits>
  9. #include <cstdlib>
  10. #include <cstring>
  11.  
  12. #include <ios>
  13. #include <iomanip>
  14. #include <fstream>
  15. #include <sstream>
  16. #include <iostream>
  17. #include <streambuf>
  18.  
  19. #include <new>
  20. #include <locale>
  21. #include <memory>
  22. #include <numeric>
  23. #include <utility>
  24. #include <iterator>
  25. #include <typeinfo>
  26. #include <algorithm>
  27. #include <exception>
  28. #include <stdexcept>
  29. #include <functional>
  30.  
  31. #include <map>
  32. #include <set>
  33. #include <list>
  34. #include <deque>
  35. #include <queue>
  36. #include <stack>
  37. #include <bitset>
  38. #include <string>
  39. #include <vector>
  40. #include <complex>
  41.  
  42. #if ((defined (__GNUC__) && __cplusplus >= 201103L) || (defined (_MSC_VER) && __cplusplus >= 199711))
  43. #   include <array>
  44. #   include <regex>
  45. #   include <tuple>
  46. #   include <random>
  47. #   include <typeindex>
  48. #   include <type_traits>
  49. #   include <forward_list>
  50. #   include <unordered_map>
  51. #   include <unordered_set>
  52. #   include <initializer_list>
  53.  
  54. #   if (!defined (_MSC_VER))
  55. #       include <mutex>
  56. #       include <ratio>
  57. #       include <atomic>
  58. #       include <chrono>
  59. #       include <future>
  60. #       include <thread>
  61. #       include <condition_variable>
  62. #   endif
  63. #endif
  64.  
  65. ///////////////////////////////////////////////////////////////////////////////////////////////////
  66. const char * INPUTFILE       = NULL;
  67. const char * OUTPUTFILE      = NULL;
  68. const char * ERROR_LOG__FILE = NULL;
  69.  
  70. const FILE * INPUT           = (INPUTFILE       ? freopen (INPUTFILE,       "r", stdin)  : stdin);
  71. const FILE * OUTPUT          = (OUTPUTFILE      ? freopen (OUTPUTFILE,      "w", stdout) : stdout);
  72. const FILE * ERROR_LOG       = (ERROR_LOG__FILE ? freopen (ERROR_LOG__FILE, "w", stderr) : stderr);
  73. ///////////////////////////////////////////////////////////////////////////////////////////////////
  74.  
  75. inline double TIME () {
  76.     return (static_cast < double > (clock ())) / (static_cast < double > (CLOCKS_PER_SEC));
  77. }
  78.  
  79. #if (defined (__GNUC__) && __cplusplus >= 201103L)
  80. using namespace std :: chrono;
  81. #endif
  82.  
  83. using namespace std;
  84.  
  85. const int MAX_N = (int) 1e5;
  86. const int MAX_Q = (int) 5e4;
  87. const int SQRT_N = 350;
  88.  
  89. int t, n, c, q;
  90. int a [MAX_N];
  91.  
  92. struct query {
  93.     int l, r, id;
  94.     bool operator < (const query & a) const {
  95.         if (l / SQRT_N != a.l / SQRT_N) {
  96.             return l / SQRT_N < a.l / SQRT_N;
  97.         } else {
  98.             return r < a.r;
  99.         }
  100.     }
  101. } qr [MAX_Q];
  102. pair < int, int > ans [MAX_Q];
  103. int l, r;
  104.  
  105. int cnt [MAX_N], ptr;
  106. int cntcnt [MAX_N + MAX_N + 1];
  107.  
  108. inline void add (const int & id) {
  109.     -- cntcnt [cnt [a [id]] + MAX_N];
  110.     ++ cnt [a [id]];
  111.     ++ cntcnt [cnt [a [id]] + MAX_N];
  112.     if (ptr < cnt [a [id]]) {
  113.         ++ ptr;
  114.     }
  115. }
  116.  
  117. inline void del (const int & id) {
  118.     -- cntcnt [cnt [a [id]] + MAX_N];
  119.     -- cnt [a [id]];
  120.     ++ cntcnt [cnt [a [id]] + MAX_N];
  121.     if (cntcnt [ptr + MAX_N] == 0) {
  122.         -- ptr;
  123.     }
  124. }
  125.  
  126. inline void SolveOrDie () /* noexcept */ {
  127.     scanf ("%d", &t);
  128.     for (int test = 1; test <= t; ++ test) {
  129.         scanf ("%d%d%d", &n, &c, &q);
  130.         for (int i = 0; i < n; ++ i) {
  131.             scanf ("%d", &a [i]);
  132.             -- a [i];
  133.         }
  134.         for (int i = 0; i < q; ++ i) {
  135.             scanf ("%d%d", &qr [i].l, &qr [i].r);
  136.             -- qr [i].l; -- qr [i].r;
  137.             qr [i].id = i;
  138.         }
  139.         sort (qr, qr + q);
  140.  
  141.         memset (cnt, 0, sizeof cnt);
  142.         memset (cntcnt, 0, sizeof cntcnt);
  143.         cntcnt [0] = n;
  144.         ptr = 0;
  145.         l = r = 0;
  146.  
  147.         add (l);
  148.         for (int i = 0; i < q; ++ i) {
  149.             while (l > qr [i].l) {
  150.                 -- l;
  151.                 add (l);
  152.             }
  153.             while (l < qr [i].l) {
  154.                 del (l);
  155.                 ++ l;
  156.             }
  157.             while (r > qr [i].r) {
  158.                 del (r);
  159.                 -- r;
  160.             }
  161.             while (r < qr [i].r) {
  162.                 ++ r;
  163.                 add (r);
  164.             }
  165.             ans [i].second = ptr;
  166.             ans [i].first = qr [i].id;
  167.         }
  168.         sort (ans, ans + q);
  169.         printf ("Case %d:\n", test);
  170.         for (int i = 0; i < q; ++ i) {
  171.             printf ("%d\n", ans [i].second);
  172.         }
  173.     }
  174. }
  175.  
  176. int main (const int argc, const char ** argv) /* noexcept */ {
  177.     assert (INPUT);
  178.     try {
  179.         SolveOrDie ();
  180.     } catch (const exception & e) {
  181.         cerr << e.what () << endl;
  182.         exit (-1);
  183.     } catch (...) {
  184.         cerr << "Exception\n";
  185.         exit (-1);
  186.     }
  187.     return 0;
  188. }
Success #stdin #stdout 0s 5644KB
comments (?)
stdin 
3
10 3 4
1 1 1 3 3 3 3 2 2 2
1 5
1 6
1 7
7 9
3 3 1
3 2 1
1 1
3 1 2  
1 1 1  
1 3  
2 2
stdout 
Case 1:
3
3
4
2
Case 2:
1
Case 3:
3
1
https://ideone.com/oSZsLB
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!