Submission #590990

#	Time	Username	Problem	Language	Result	Execution time	Memory
590990		nguyen31hoang08minh2003	Po (COCI21_po)	C++14	70 / 70	19 ms	18976 KiB

Main

/*
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|
|  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / |
| /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |
|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |
| \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |  / | \  |
|  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ | /  |  \ |
|   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (signed i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (signed i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (signed i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

const int maxN = 100005;

int n, a[maxN], Log2[maxN];
ii spt[20][maxN];

ii query(int l, int r) {
    const int &j = Log2[r - l + 1];
    return min(spt[j][l], spt[j][r - (1 << j) + 1]);
}

int rec(int l, int r) {
    if (l > r)
        return 0;
    const int val = query(l, r).fi;
    int res = (val > 0);
    while (l <= r) {
        if (a[l] == val) {
            ++l;
            continue;
        }
        const auto [v, p] = query(l, r);
        if (v == val) {
            res += rec(l, p - 1);
            l = p + 1;
        } else {
            res += rec(l, r);
            break;
        }
    }
    return res;
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cin >> n;
    fort(i, 1, n) {
        cin >> a[i];
        spt[0][i] = make_pair(a[i], i);
    }
    fort(i, 2, n)
        Log2[i] = Log2[i >> 1] + 1;
    for (int j = 1; (1 << j) <= n; ++j)
        fort(i, 1, n - (1 << j) + 1)
            spt[j][i] = min(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
    cout << rec(1, n) << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int rec(int, int)':
Main.cpp:58:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         const auto [v, p] = query(l, r);
      |                    ^
Main.cpp: In function 'int main()':
Main.cpp:85:67: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   85 |             spt[j][i] = min(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                                 ~~^~~

• Subtask 1: 70 / 70