fork download
copy 
  1. /**
  2.  *    author:  orzvanh14
  3.  *    created: 23.12.2022 10:08:02
  4.  *    too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define fi first
  16. #define se second
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define eb emplace_back
  20. #define pb push_back
  21. #define TASK " "
  22.  
  23. #define ms(a, x) memset(a, x, sizeof(a))
  24. #define all(a) a.begin(), a.end()
  25. #define All(a, n) a + 1, a + 1 + n
  26.  
  27. #define LOG 19
  28.  
  29.  
  30. const int INF = 1e18;
  31. const int mod = 1e9+7;
  32. const int N = 2e5  + 5;
  33. const int maxN = 3e5 + 5;
  34. int MOD = 998244353;
  35. int bit[200000];
  36. struct node{
  37. 	int kc, u, hk;
  38. 	bool operator<(const node& other) const {
  39.         return kc > other.kc; 
  40.     }
  41. };
  42. struct edge{
  43. 	int u, v, w, id;
  44. 	friend bool operator < ( edge a, edge b){
  45. 		return a.w > b.w;
  46. 	}
  47. };
  48. int n,q;
  49. int a[N];
  50. int st[4 * N];
  51. void nhap(){
  52.     cin >> n;
  53. 	for(int i = 1;i <= n; i++){
  54. 		cin >> a[i];
  55. 	}
  56. }
  57. void build(int id, int l,int r){
  58. 	if(l == r){
  59. 		st[id] = a[l];
  60. 	}
  61. 	else{
  62. 		int m = l + r >> 1;
  63. 		build(2 * id, l, m);
  64. 		build(2 * id + 1, m + 1, r);
  65. 		st[id] = max(st[2 * id], st[2 * id + 1]);
  66. 	}
  67. }
  68. void update(int id, int l,int r, int i, int val){
  69. 	if(l > i || i > r){
  70. 		return;
  71. 	}
  72. 	if(l == r){
  73. 		st[id] = val;
  74. 		return;
  75. 	}
  76. 	else{
  77. 		int m = l + r >> 1;
  78. 		update(2 * id, l, m, i, val);
  79. 		update(2 * id + 1, m + 1, r, i, val);
  80. 		st[id] = max(st[2 * id], st[2 * id + 1]);
  81. 	}
  82. }
  83. int get(int id, int l, int r, int u, int v){
  84. 	if(l > v || r < u) return -INF;
  85. 	if(l >= u && r <= v){
  86. 		return st[id];
  87. 	}
  88. 	else{
  89. 		int m = l + r >> 1;
  90. 		return max(get(2 * id, l, m, u, v), get(2 * id + 1, m + 1, r, u, v));
  91. 	}
  92. }
  93. void solve(){
  94.     int ok = 0;
  95. 	build(1, 1, n);
  96. 	for(int i = 1; i <= n; i++){
  97.               int l, r; cin >> l >> r;
  98.               int mx = get(1, 1, n, l, r);
  99.               if(a[i] >= mx){
  100.                   ok = i;
  101.                   continue;
  102.               }
  103.               else{
  104.                   a[i] = mx;
  105.                   update(1, 1, n, i, a[i]);
  106.                   ok = 0;
  107.               }
  108.           }
  109.           cout << ok;
  110.  
  111. }
  112. signed main() {
  113. 	// freopen("piggyback.in", "r", stdin);
  114. 	// freopen("piggyback.out", "w", stdout);
  115. 	ios_base::sync_with_stdio(0);
  116. 	cin.tie(0);
  117. 	cout.tie(0);
  118.     nhap();
  119.     solve();
  120. 	return 0;
  121.  
  122. }
  123.  
Success #stdin #stdout 0s 5544KB
comments (?)
stdin
copy 
4
1 2 3 4
2 2
3 3
1 2
1 3
stdout
copy 
4
https://ideone.com/mAG0gi
language:
C++14 (gcc 8.3)
created:
7 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!