Submission #382758

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
382758	2021-03-28T07:03:56 Z	ne4eHbKa	Po (COCI21_po)	C++17	70 / 70	50 ms	20716 KB

Main

#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

const int N = 1e5 + 5;
int n, a[N], s[N][20], lg[N];

int mn(int i, int j) {return a[j] < a[i] ? j : i;}

int get(int l, int r) {
    int f = lg[r - l];
    return mn(s[l][f], s[r - (1 << f)][f]);
}

int rec(int l = 0, int r = n) {
    vector<int> f;
    f.push_back(l - 1);
    int i = l;
    while(i < r) {
        int j = get(i, r);
        if(len(f) > 1 && a[f.back()] != a[j]) break;
        f.push_back(j);
        i = j + 1;
    }
    f.push_back(r);
    int ans = !!a[f[1]];
    for(int i = 1; i < len(f); ++i)
        if(f[i - 1] + 1 < f[i])
            ans += rec(f[i - 1] + 1, f[i]);
    return ans;
}

void solve() {
    for(int i = 0; i < N; ++i)
        lg[i] = !i ? 0 : lg[i - 1] +
            (1 << lg[i - 1] + 1 <= i);
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i], s[i][0] = i;
    for(int i = 1; i < 20; ++i)
        for(int j = 0; j + (1 << i) <= n; ++j)
            s[j][i] = mn(s[j][i - 1],
                         s[j + (1 << i - 1)][i - 1]);
    cout << rec() << endl;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:61:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   61 |             (1 << lg[i - 1] + 1 <= i);
      |                   ~~~~~~~~~~^~~
Main.cpp:68:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   68 |                          s[j + (1 << i - 1)][i - 1]);
      |                                      ~~^~~

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	748 KB	Output is correct
3	Correct	2 ms	876 KB	Output is correct
4	Correct	14 ms	4844 KB	Output is correct
5	Correct	23 ms	6892 KB	Output is correct
6	Correct	38 ms	16748 KB	Output is correct
7	Correct	50 ms	20716 KB	Output is correct