fork download
copy 
  1. /*input
  2. 5 3
  3. 1 1 1 1 1
  4. 1 2 2
  5. 1 3 2
  6. 1 4 5
  7. */
  8. #include<bits/stdc++.h>
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. #include <ext/pb_ds/tree_policy.hpp>
  11. using namespace std;
  12. using namespace __gnu_pbds;
  13.  
  14. #define int long long 
  15. #define double long double
  16. #define f first
  17. #define s second
  18. #define mp make_pair
  19. #define pb push_back
  20.  
  21. #define RE(i,n) for (int i = 1; i <= n; i++)
  22. #define RED(i,n) for (int i = n; i > 0; i--)
  23. #define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
  24. #define REP(i,n) for (int i = 0; i < (int)n; i++)
  25. #define FOR(i,a,b) for (int i = a; i < b; i++)
  26. #define REPD(i,n) for (int i = n-1; i >= 0; i--)
  27. #define FORD(i,a,b) for (int i = a; i >= b; i--)
  28.  
  29. #define all(v) v.begin(),v.end()
  30. #define pii pair<int,int>
  31. #define vi vector<int>
  32. #define vvi vector<vi>
  33. #define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
  34. #define debug(x) cout << x << endl;
  35. #define debug2(x,y) cout << x << " " << y << endl;
  36. #define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
  37.  
  38. typedef tree<
  39. int,
  40. null_type,
  41. less<int>,
  42. rb_tree_tag,
  43. tree_order_statistics_node_update>
  44. ordered_set;
  45.  
  46. const int INF = 1e18+1;
  47. const int MOD = 1e9+7;
  48. const double PI = 3.14159265358979323846264338;
  49.  
  50. int raise(int a,int n,int m = MOD){
  51.   if(n == 0)return 1;
  52.   if(n == 1)return a;
  53.   int x = 1;
  54.     x *= raise(a,n/2,m);
  55.     x %= m;
  56.     x *= x;
  57.     x %= m;
  58.     if(n%2)x*= a;
  59.     x %= m;
  60.     return x;
  61. }
  62.  
  63. int floor1(int n,int k){
  64.     if(n%k == 0 || n >= 0)return n/k;
  65.     return (n/k)-1;
  66. }
  67.  
  68. int ceil1(int n,int k){
  69.     return floor1(n+k-1,k);
  70. }
  71.  
  72. const int N = 1e6+1;
  73. int n,q;
  74. int a[N];
  75. set<int> starts;
  76.  
  77. void solve(){
  78.   	cin >> n >> q;
  79.   	a[0] = 0;
  80.   	RE(i,n){
  81.   		cin >> a[i];
  82.   		if(a[i] != a[i-1])starts.insert(i);
  83.   	}
  84.   	while(q--){
  85.   		int ty = 1;cin >> ty;
  86.   		//print(starts);
  87.   		if(ty == 1){
  88.   			int ind,x;cin >> ind >> x;
  89.   			auto nextbl = starts.upper_bound(ind);
  90.   			int curbl = *nextbl;curbl--;
  91.         if(ind != n and a[ind+1] == a[ind] and x != a[ind+1]){
  92.           starts.insert(ind+1);
  93.         }
  94.         if(ind != n and a[ind+1] != a[ind] and x == a[ind+1]){
  95.           starts.erase(ind+1);
  96.         }
  97.         if(ind != 1 and a[ind-1] == a[ind] and x != a[ind-1]){
  98.           starts.insert(ind);
  99.         }
  100.         if(ind != 1 and a[ind-1] != a[ind] and x == a[ind-1]){
  101.           starts.erase(ind);
  102.         }
  103.         a[ind] =x;
  104.         continue;
  105.   		}
  106.   		int ind;cin >> ind;
  107.   		auto wow = starts.upper_bound(ind);
  108.   		wow--;
  109.   		int cur = a[*wow];
  110.   		int lst = *wow;
  111.   		while(1){
  112.   			if(wow == starts.begin())break;
  113.   			wow--;
  114.   			if(cur%a[*wow] == 0){
  115.   				cur = a[*wow];
  116.   				lst = *wow;
  117.   			}
  118.   			else{
  119.   				break;
  120.   			}
  121.   		}
  122.  
  123.   		cout << lst << endl;
  124.   		//print(starts);
  125.   	}
  126. }
  127.  
  128. signed main(){
  129.   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  130.   //freopen(".in","r",stdin);freopen(".out","w",stdout);
  131.   int t = 1;
  132.   //cin >> t;
  133.   while(t--){
  134.     solve();
  135.   }
  136.   return 0;
  137. }
Success #stdin #stdout 0s 4288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MbE98h
language:
C++14 (gcc 8.3)
created:
4 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!