fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #include <vector>
  4. #include <stack>
  5. #include <queue>
  6. #include <deque>
  7. #include <utility>
  8. #include <set>
  9. #include <map>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include<algorithm>
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. #define IOF ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  16. #define ll long long
  17. #define ld long double
  18. #define cy cout << "YES" << '\n';
  19. #define cn cout << "NO" << '\n';
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23. template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  24. template<typename T>
  25. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  26.  
  27. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  28. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  29. int knightX[] = {-2, -2, 2, 2, 1, 1 , -1, -1};
  30. int knighty[] = {-1, 1, -1, 1, -2, 2, -2, 2};
  31. char di[] = {'D', 'L', 'U', 'R'};
  32. const int N =505 , M = 1e4+5;
  33. const ll MOD =  998244353;
  34. const int LOG = 20;
  35. void FOI() {
  36.       freopen("input.txt", "r", stdin);
  37.       freopen("output.txt", "w", stdout);
  38.   }
  39.  
  40.   struct segtree{
  41.     vector<ll> tree;
  42.     segtree(){
  43.       tree.resize(2048 , 0);
  44.     }
  45.     void update(int idx , ll val){
  46.       update(idx , val , 0 , 0 ,1024);
  47.     }
  48.     void update(int idx , ll val , int x , int lx , int rx){
  49.       if(rx-lx == 1){
  50.         tree[x] = idx*val;
  51.         return ;
  52.       }
  53.       int m = (lx+rx)/2;
  54.       if(idx < m){
  55.         update(idx , val , 2*x+1 , lx , m);
  56.       }
  57.       else update(idx , val , 2*x+2 , m , rx);
  58.       tree[x] = max(tree[2*x+1] , tree[2*x+2]);
  59.     }
  60.     ll get(){
  61.       return tree[0];
  62.     }
  63.  
  64.   };
  65.  
  66. void solve(){
  67. int n , q ; cin >> n >> q;
  68. vector<int> v(n);
  69. for(int i = 0 ; i < n; i++)cin >> v[i] ;
  70.     vector<vector<ll>> divs(n);
  71.     for(int j = 0 ; j< n; j++){
  72.     vector<ll> ret;
  73.     ll i;
  74.     for (i = 1; i*i <= v[j] ; ++i) {
  75.         if (v[j] % i == 0) {
  76.             ret.push_back(i);
  77.             if(i*i!= v[j])
  78.             ret.push_back(v[j] / i);
  79.         }
  80.     }
  81.     divs[j] = ret;
  82.   }
  83.   vector<set<int>> pos(1024);
  84.   for(int i = 0 ; i < n; i++){
  85.     for (auto &&d : divs[i])
  86.     {
  87.       pos[d].insert(i);
  88.     }
  89.   }
  90.   vector<int> freq(1024);
  91.   for (auto &&i : v)
  92.   {
  93.     freq[i]++;
  94.   }
  95.   segtree st;
  96.   for(int i = 1 ; i <= 1023 ; i++){
  97.     st.update(i , freq[i]);
  98.   }
  99.   while(q--){
  100.     int x , k ; cin >> x >> k;
  101.     x--;
  102.     auto &stt = pos[k];
  103.     auto it = stt.lower_bound(x);
  104.     vector<int> del;
  105.     for(; it != stt.end() ; it++){
  106.       del.push_back(*it);
  107.     }
  108.     while(del.size()){
  109.       int val = v[del.back()];
  110.       st.update(val , freq[val]-1 );
  111.       freq[val]--;
  112.       stt.erase(del.back());
  113.       for (auto &&d : divs[del.back()])
  114.       {
  115.         pos[d].erase(del.back());
  116.       }
  117.       v[del.back()] = 0;
  118.       del.pop_back();
  119.     }
  120.     cout << st.get() << '\n';
  121.   }
  122. } 
  123.  
  124.  
  125. signed main() {
  126.   IOF
  127.   //FOI();
  128.   //freopen("substr.in", "r", stdin);
  129.     ll t = 1;
  130.     cin >> t;
  131.     while (t--) {
  132.  
  133.     solve() ;
  134.  
  135.     }
  136.  
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sJ3gAq
language:
C++ (gcc 8.3)
created:
2 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!