Editorial for Lại là dãy số.
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <bits/stdc++.h> using namespace std; int n, k, a[1000100], l[1000100], r[1000100]; int main() { ios::sync_with_stdio(0); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; l[1] = 1; for (int i = 2; i <= n; i++) if (a[i] < a[i - 1]) l[i] = i; else { l[i] = l[i - 1]; while (l[i] > 1 && a[l[i] - 1] <= a[i]) l[i] = l[l[i] - 1]; } r[n] = n; for (int i = n - 1; i; i--) if (a[i] <= a[i + 1]) r[i] = i; else { r[i] = r[i + 1]; while (r[i] < n && a[r[i] + 1] < a[i]) r[i] = r[r[i] + 1]; } long long ans = 0; for (int i = 1; i <= n; i++) if (a[i] == k) ans += (i - l[i] + 1LL) * (r[i] - i + 1); cout << ans << endl; }
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it) #define RESET(a, v) memset((a), (v), sizeof((a))) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int N = 1000006; using namespace std; int a[N], L[N], R[N]; int n, k; int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> k; REP(i, 1, n) cin >> a[i]; a[0] = a[n + 1] = INT_MAX; REP(i, 1, n) for(L[i] = i - 1; a[L[i]] < a[i]; L[i] = L[L[i]]); REPD(i, n, 1) for(R[i] = i + 1; a[R[i]] <= a[i]; R[i] = R[R[i]]); LL ans = 0; REP(i, 1, n) if (a[i] == k) ans += (LL)(i - L[i]) * (R[i] - i); cout << ans; return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define Fit(i,c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++) #define inf 1000000005 #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) #define mod 1000000007 #define sz(a) ((int)(a).size()) template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return __builtin_popcountll(s);} #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) typedef unsigned long long ull; typedef long long ll; typedef double ld; #define eps 1e-9 typedef pair<int, int> II; template<class T> T gcd(T a, T b){ T r; while (b != 0) { r = a % b; a = b; b = r; } return a;} template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } #define PI 2 * acos(0) #define maxn 2000005 int n, k, a[maxn]; int main() { // freopen("jingles.in", "r", stdin); // freopen("jingles.out", "w", stdout); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; For(i, 1, n) cin >> a[i]; int u = 0, v = 0; ll res = 0; For(i, 1, n){ if(a[i] > k){ u = i; v = i; } if(a[i] == k){ u = i; } res += u - v; } cout << res << "\n"; return 0; }
Comments