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.

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

Please read the guidelines before commenting.


There are no comments at the moment.