fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define     filename "thaotac"
  5.  
  6. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  7. #define     nl "\n"
  8. #define     sp " "
  9. #define     yes "YES"
  10. #define     no "NO"
  11. #define     impossible "IMPOSSIBLE"
  12.  
  13. #define     pb push_back
  14. #define     popb pop_back
  15. #define     all(v) (v).begin(), (v).end()
  16. #define     fi first
  17. #define     se second
  18. //-1 neu x = 0
  19. #define     bit_count(x) (__builtin_popcountll(x))
  20.  
  21. #define     GCD(a,b) (__gcd((a),(b)))
  22. #define     LCM(a,b) ((a) / __gcd((a),(b)) * (b))
  23.  
  24.  
  25. #define     for_in_set(se) for(auto it = (se).begin(); it != (se).end(); ++it)
  26. #define     rnd(l,r) ((l) + rd() % ((r) - (l) + 1))
  27.  
  28. typedef long long ll;
  29. const int mod   = 1e9 + 7;
  30. const int maxn  = 2e5;
  31. const int INF   = 1e9 + 5;
  32. const ll  LLINF = 1e18 + 5;
  33.  
  34. int n, q, f[100005][11];
  35. ll a[100005], grid[1001][1001], prefixsum[1001][1001], modulo_table[11][11];
  36. void read() {
  37.     cin >> n >> q;
  38.     for (int i = 1; i<=n; ++i) cin >> a[i];
  39. }
  40.  
  41. void sub1() {
  42.     for (int hihi = 0; hihi<q; ++hihi) {
  43.         int l, r; cin >> l >> r;
  44.         ll res = 0;
  45.         for (int i = l; i<=r; ++i) {
  46.             for (int j = l; j<=r; ++j) {
  47.                 res += a[i] % a[j];
  48.             }
  49.         }
  50.         cout << res << nl;
  51.     }
  52. }
  53. void sub3() {
  54.     for (int i = 1; i<=n; ++i) {
  55.         for (int j = 1; j<=n; ++j) {
  56.             grid[i][j] = a[i] % a[j];
  57.         }
  58.     }
  59.  
  60.     for (int i = 1; i<=n; ++i) {
  61.         for (int j = 1; j<=n; ++j) {
  62.             prefixsum[i][j] = grid[i][j] + prefixsum[i-1][j] + prefixsum[i][j-1] - prefixsum[i-1][j-1];
  63.         }
  64.     }
  65.  
  66.     for (int i = 0; i<q; ++i) {
  67.         int l, r; cin >> l >> r;
  68.         int x1 = l, y1 = l, x2 = r, y2 = r;
  69.         ll res = prefixsum[r][r] + prefixsum[l-1][l-1] - prefixsum[r][l-1] - prefixsum[l-1][r];
  70.         cout << res << nl;
  71.     }
  72. }
  73. void sub2() {
  74.     for (int i = 1; i<=n; ++i) {
  75.         for (int j = 1; j<=10; ++j) f[i][j] = f[i-1][j];
  76.         ++f[i][a[i]];
  77.     }
  78.     for (int i = 1; i<=10; ++i) {
  79.         for (int j = 1; j<=10; ++j) modulo_table[i][j] = i % j;
  80.     }
  81.     while (q--) {
  82.         int l, r; cin >> l >> r;
  83.         ll res = 0;
  84.         vector <int> freq;
  85.         freq.push_back(0);
  86.         for (int i = 1; i<=10; ++i) freq.pb(f[r][i] - f[l-1][i]);
  87.  
  88.         for (int i = 1; i<=10; ++i) {
  89.             for (int j = 1; j<=10; ++j) {
  90.                 res += freq[i] * freq[j] * modulo_table[i][j];
  91.             }
  92.         }
  93.         cout << res << nl;
  94.     }
  95. }
  96. void sub4(int maxval) {
  97.  
  98. }
  99. void solve() {
  100.     int g = *max_element(a+1, a+n+1);
  101.     if (n <= 100 && q <= 100) sub1();
  102.     else if (n <= 5e4 && q <= 1e5 && g <= 10) sub2();
  103.     else if (n <= 1e3 && q <= 1e5 && g <= 1e5) sub3();
  104.     else sub4(g);
  105. }
  106. int main() {
  107.     ios_base::sync_with_stdio(false);
  108.     cin.tie(0); cout.tie(0);
  109.  
  110.     if (fopen(filename ".inp", "r")) {
  111.         freopen(filename ".inp", "r", stdin);
  112.         freopen(filename ".out", "w", stdout);
  113.     }
  114.  
  115.     int t = 1;
  116.     //cin >> t;
  117.     while (t--) {
  118.         read();
  119.         solve();
  120.         cout << nl;
  121.     }
  122.  
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/40hQi6
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
3 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!