fork download
copy 
  1. // #define _CRT_SECURE_NO_WARNINGS 
  2.  
  3. #include <iostream> 
  4. #include <algorithm> 
  5. #include <cmath> 
  6. #include <climits> 
  7. #include <vector> 
  8. #include <queue> 
  9. #include <deque> 
  10. #include <array> 
  11. #include <list> 
  12. #include <stack> 
  13. #include <tuple> 
  14. #include <set> 
  15. #include <unordered_set> 
  16. #include <map> 
  17. #include <unordered_map> 
  18. #include <string> 
  19. #include <cstring> 
  20. #include <random> 
  21. #include <bitset> 
  22. #include <iomanip> 
  23. #include <iterator> 
  24. #include <functional> 
  25. #include <ctime> 
  26. #include <chrono> 
  27. #include <cctype> 
  28. #include <fstream> 
  29. #include <ranges> 
  30. #include <numeric> 
  31. #include <complex> 
  32. #include <cassert> 
  33.  
  34. using namespace std;
  35.  
  36. // #pragma GCC optimize("Ofast") 
  37. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  38.  
  39. #define int               long long 
  40. #define sz(x)             ((int)(x).size()) 
  41. #define mp                make_pair 
  42. #define all(x)            (x).begin(), (x).end() 
  43. #define pb                push_back 
  44. #define pf                push_front 
  45. #define ff                first 
  46. #define ss                second 
  47. #define unique(x)         (x).erase(unique(all(x)), (x).end()) 
  48. #define min3(a, b, c)     min(a, min(b, c)) 
  49. #define max3(a, b, c)     max(a, max(b, c)) 
  50. #define FOR(i, a, b)      for (int i = (a); i <= (b); i++) 
  51. #define ROF(i, a, b)      for (int i = (a); i >= (b); i--) 
  52.  
  53. using vi = vector<int>;
  54. using vd = vector<double>;
  55. using vpii = vector<pair<int, int>>;
  56. using vpdd = vector<pair<double, double>>;
  57. using pii = pair<int, int>;
  58. using pdd = pair<double, double>;
  59.  
  60. template <typename Container>
  61. void PRINT(const Container& container) {
  62.     for (const auto& e : container) {
  63.         cout << e << ' ';
  64.     } cout << '\n';
  65. }
  66.  
  67. void print_double(double ans, int num) {
  68.     cout << fixed << setprecision(num) << ans << '\n';
  69. }
  70.  
  71. const int inf = 1e18;
  72. const double eps = 1e-9;
  73. const double PI = 3.141592653589793;
  74.  
  75. string alh = "abcdefghijklmnopqrstuvwxyz";
  76. string ALH = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  77.  
  78. int BLOCK_SIZE = 1000;
  79.  
  80. class Mo {
  81. public:
  82.     struct QUERY {
  83.         int l;
  84.         int r;
  85.         int id;
  86.  
  87.         bool operator<(const QUERY& other) const {
  88.             int block1 = l / BLOCK_SIZE;
  89.             int block2 = other.l / BLOCK_SIZE;
  90.  
  91.             if (block1 != block2) {
  92.                 return block1 < block2;
  93.             }
  94.  
  95.             if (block1 % 2 == 1) {
  96.                 return r < other.r;
  97.             }
  98.             else {
  99.                 return r > other.r;
  100.             }
  101.         }
  102.     };
  103.  
  104.  
  105.  
  106.  
  107.  
  108.     // --- STATE --- //
  109.  
  110.     map<int, int> cnt;
  111.     int z = 0;
  112.  
  113.     void ADD(int G) {
  114.         cnt[a[G]] += 1;
  115.  
  116.         if (cnt[a[G]] == 0) {
  117.             // no changes
  118.         }
  119.         else if (cnt[a[G]] == 1) {
  120.             ++z;
  121.         }
  122.         else if (cnt[a[G]] == 2) {
  123.             --z;
  124.         }
  125.         else {
  126.             // no changes
  127.         }
  128.     }
  129.  
  130.     void REM(int G) {
  131.         cnt[a[G]] -= 1;
  132.  
  133.         if (cnt[a[G]] == 0) {
  134.             --z;
  135.         }
  136.         else if (cnt[a[G]] == 1) {
  137.             ++z;
  138.         }
  139.         else if (cnt[a[G]] == 2) {
  140.             // no changes
  141.         }
  142.         else {
  143.             // no changes
  144.         }
  145.     }
  146.  
  147.     void add_right() {
  148.         R++;
  149.         ADD(R);
  150.     }
  151.  
  152.     void add_left() {
  153.         L--;
  154.         ADD(L);
  155.     }
  156.  
  157.     void rem_right() {
  158.         REM(R);
  159.         R--;
  160.     }
  161.  
  162.     void rem_left() {
  163.         REM(L);
  164.         L++;
  165.     }
  166.  
  167.     auto get_ans() {
  168.         return z;
  169.     }
  170.  
  171.     // --- STATE --- //
  172.  
  173.  
  174.  
  175.  
  176.  
  177.     Mo(vector<pair<int, int>> Q_, vector<int> a_) : a(a_) {
  178.         BLOCK_SIZE = (int)sqrt((int)a.size()) + 1;
  179.  
  180.         for (int i = 0; i < (int)Q_.size(); i++) {
  181.             Q.push_back({ Q_[i].first, Q_[i].second, i });
  182.         }
  183.         sort(Q.begin(), Q.end());
  184.  
  185.         ans.resize((int)Q.size());
  186.         L = 0; R = -1;
  187.     }
  188.  
  189.     void GO() {
  190.         for (int i = 0; i < (int)ans.size(); i++) {
  191.             while (R < Q[i].r) {
  192.                 add_right();
  193.             }
  194.  
  195.             while (L > Q[i].l) {
  196.                 add_left();
  197.             }
  198.  
  199.             while (R > Q[i].r) {
  200.                 rem_right();
  201.             }
  202.  
  203.             while (L < Q[i].l) {
  204.                 rem_left();
  205.             }
  206.  
  207.             ans[Q[i].id] = get_ans();
  208.         }
  209.     }
  210.  
  211.     void print_ans() {
  212.         for (auto p : ans) {
  213.             cout << p << '\n';
  214.         }
  215.     }
  216.  
  217. private:
  218.     vector<int> ans;
  219.  
  220.     vector<QUERY> Q;
  221.     vector<int> a;
  222.  
  223.     int L, R;
  224. };
  225.  
  226. void Solve() {
  227.     int n; cin >> n;
  228.     vector<int> a(n);
  229.     for (int i = 0; i < n; i++) {
  230.         cin >> a[i];
  231.     }
  232.  
  233.     vector<pair<int, int>> Q;
  234.  
  235.     int q; cin >> q;
  236.     for (int i = 0; i < q; i++) {
  237.         int l, r; cin >> l >> r;
  238.         --l;
  239.         --r;
  240.         Q.push_back({ l, r });
  241.     }
  242.  
  243.     Mo W(Q, a); W.GO();
  244.     W.print_ans();
  245. }
  246.  
  247. signed main() {
  248.     ios_base::sync_with_stdio(false);
  249.     cin.tie(0);
  250.     cout.tie(0);
  251.  
  252.     /*
  253.                       ________________
  254.                      / Just solved it \
  255.                      |   in my mind   |
  256.                      \________________/
  257.                     /
  258.                    /
  259. 　　　　　／＞　 フ         ___________
  260. 　　　　　| 　_　 _|       |          |
  261. 　 　　　／`ミ _x 彡       |   WA 2   |
  262. 　　 　 /　　　 　 |       |__________|
  263. 　　　 /　 ヽ　　 ﾉ        /          /
  264. 　／￣|　　 |　|　|       /_________ /
  265. 　| (￣ヽ＿_ヽ_)_)
  266. 　＼二つ
  267.  
  268.     */
  269.  
  270.     /*
  271.     freopen("input.txt", "r", stdin);
  272.     freopen("output.txt", "w", stdout);
  273.     */
  274.  
  275.     // auto start = chrono::high_resolution_clock::now();
  276.  
  277.     int multitest = false;
  278.     if (multitest == true) {
  279.         int ctt; cin >> ctt;
  280.  
  281.         for (int i = 0; i < ctt; i++) {
  282.             Solve();
  283.         }
  284.     }
  285.     else {
  286.         Solve();
  287.     }
  288.  
  289.     // auto end = chrono::high_resolution_clock::now();
  290.  
  291.     /*
  292.     cout << "Time taken: "
  293.          << chrono::duration_cast<chrono::milliseconds>(end - start).count()
  294.          << " milliseconds" << endl;
  295.     */
  296.  
  297.     return 0;
  298. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:29:10: fatal error: ranges: No such file or directory
 #include <ranges>
          ^~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/o9LL2q
language:
C++14 (gcc 8.3)
created:
324 days 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!