fork download
copy 
  1. /*                ___
  2.    _______________| |_
  3.   /\                  \
  4.  /  \                  \
  5. /____\__________________\
  6. |    |                  |
  7. |    | Date : 23/07/2025|
  8. |    | Author : pppssslc|
  9. |____|__________________|
  10. */
  11. #include<bits/stdc++.h>
  12.  
  13. using namespace std;
  14.  
  15. typedef string str;
  16. typedef long long ll;
  17. typedef unsigned long long ull;
  18. typedef double db;
  19. typedef long double ldb;
  20. typedef pair<int, int> pii;
  21. typedef pair<ll, ll> pll;
  22. typedef vector<int> vi;
  23. typedef vector<ll> vl;
  24. typedef vector<vector<int>> vii;
  25. typedef vector<vector<ll>> vll;
  26. typedef map<int, int> mpii;
  27. typedef map<ll, ll> mpll;
  28. typedef set<int> si;
  29. typedef set<ll> sl;
  30. #define prio_que priority_queue
  31.  
  32. #define se second
  33. #define fi first
  34. #define For(i, l, r, x) for(int i = l; i <= r; i += x)
  35. #define Ford(i, l, r, x) for(int i = l; i >= r; i -= x)
  36. #define Fore(x, a) for(auto x: a)
  37. #define pb push_back
  38. #define ins insert
  39. #define all(a) a.begin(), a.end()
  40.  
  41. const ll inf = 1e18 + 1;
  42. const int mod = 1e9 + 7;
  43. const int maxn = 2e5 + 1;
  44.  
  45. vi val[maxn];
  46. int bit[maxn], l[maxn], r[maxn], u[maxn], v[maxn], res[maxn];
  47. int n, q;
  48.  
  49. void upd(int p){
  50. 	For(i, p, n, i&-i) ++bit[i];
  51. }
  52.  
  53. int get(int p){
  54. 	int ret = 0;
  55. 	if(p == 0) return 0;
  56. 	Ford(i, p, 1, i&-i) ret += bit[i];
  57. 	return ret;
  58. }
  59.  
  60. int main(){
  61. 	ios_base::sync_with_stdio(false);
  62. 	cin.tie(NULL); cout.tie(NULL);
  63. 	cin >> n >> q;
  64. 	memset(res, -1, sizeof(res));
  65. 	For(i, 1, n, 1){
  66. 		int a; cin >> a;
  67. 		val[a].pb(i);
  68. 	}
  69. 	For(i, 1, q, 1){
  70. 		cin >> u[i] >> v[i];
  71. 		l[i] = 1, r[i] = n;
  72. 	}
  73. 	while(true){
  74. 		memset(bit, 0, sizeof(bit));
  75. 		bool check = true;
  76. 		vi qrs[n + 1];
  77. 		For(i, 1, q, 1){
  78. 			if(l[i] <= r[i]) check = false;
  79. 			else continue;
  80. 			qrs[(l[i] + r[i]) / 2].pb(i);
  81. 		}
  82. 		if(check) break;
  83. 		Ford(i, n, 1, 1){
  84. 			Fore(id, val[i])upd(id);
  85. 			Fore(id, qrs[i]){
  86. 				if(get(v[id]) - get(u[id] - 1) >= i){
  87. 					l[id] = i + 1;
  88. 					res[id] = i;
  89. 				}else r[id] = i - 1;
  90. 			}
  91. 		}
  92. 	}
  93. 	For(i, 1, q, 1) cout << res[i] << '\n';
  94. 	return (0 ^ 0);
  95. }
Success #stdin #stdout 0.01s 12884KB
comments (?)
stdin
copy 
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
stdout
copy 
1
3
3
1
2
2
https://ideone.com/kaj4lT
language:
C++ (gcc 8.3)
created:
8 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!