Submission #405159

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
405159	2021-05-15T19:35:17 Z	Falcon	Money (IZhO17_money)	C++17	100 / 100	1272 ms	65892 KB

money

#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.hpp"
#endif

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)

#ifdef DEBUG
#define debug(x...)         { \
                            ++dbg::depth; \
                            string dbg_vals = dbg::to_string(x); \
                            --dbg::depth; \
                            dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
                            }

#define light_debug(x)      { \
                            dbg::light = true; \
                            dbg::dout << __func__ << ":" << __LINE__; \
                            dbg::dout << "  " << #x << " = " << x << endl; \
                            dbg::light = false; \
                            }

#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


using ll = long long;

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

class fenwick_tree {
        
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    vector<int> a(n); rep(i, n) cin >> a[i];
    reverse(all(a)); rep(i, n) a[i] = 1000000 - a[i];
    map<int, int> m;
    vector<int> x(n), y(n);
    rrep(i, n) {
        auto p = m.lower_bound(a[i]);
        x[i] = p == m.end() ? n : p->second;
        p = m.upper_bound(a[i]);
        y[i] = p == m.end() ? n : p->second;
        m[a[i]] = i;
    }

    debug(a, x, y);

    int c{};
    for(int i{}; i < n;) {
        int j{i};
        ++c;
        while(j + 1 < n && a[j + 1] == a[i]) ++j;
        if(j + 1 == y[j]) {
            ++j;
            while(j + 1 < n && j + 1 == x[j]) ++j;
        }
        debug(i, j);
        i = j + 1;
    }

    cout << c << '\n';
    
    
    #ifdef DEBUG
    dbg::dout << "\nExecution time: "
              << clock() * 1000 / CLOCKS_PER_SEC 
              << "ms" << endl;
    #endif
    return 0;
}

Compilation message

money.cpp: In function 'int main()':
money.cpp:33:29: warning: statement has no effect [-Wunused-value]
   33 | #define debug(x...)         42
      |                             ^~
money.cpp:67:5: note: in expansion of macro 'debug'
   67 |     debug(a, x, y);
      |     ^~~~~
money.cpp:33:29: warning: statement has no effect [-Wunused-value]
   33 | #define debug(x...)         42
      |                             ^~
money.cpp:78:9: note: in expansion of macro 'debug'
   78 |         debug(i, j);
      |         ^~~~~

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	312 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	312 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	312 KB	Output is correct
19	Correct	1 ms	304 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	308 KB	Output is correct
22	Correct	1 ms	312 KB	Output is correct
23	Correct	1 ms	308 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	312 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	312 KB	Output is correct
19	Correct	1 ms	304 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	308 KB	Output is correct
22	Correct	1 ms	312 KB	Output is correct
23	Correct	1 ms	308 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	1 ms	204 KB	Output is correct
29	Correct	1 ms	204 KB	Output is correct
30	Correct	1 ms	204 KB	Output is correct
31	Correct	1 ms	204 KB	Output is correct
32	Correct	1 ms	204 KB	Output is correct
33	Correct	1 ms	312 KB	Output is correct
34	Correct	1 ms	204 KB	Output is correct
35	Correct	1 ms	204 KB	Output is correct
36	Correct	1 ms	316 KB	Output is correct
37	Correct	1 ms	204 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct

Subtask #4
55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	312 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	312 KB	Output is correct
19	Correct	1 ms	304 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	308 KB	Output is correct
22	Correct	1 ms	312 KB	Output is correct
23	Correct	1 ms	308 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	1 ms	204 KB	Output is correct
29	Correct	1 ms	204 KB	Output is correct
30	Correct	1 ms	204 KB	Output is correct
31	Correct	1 ms	204 KB	Output is correct
32	Correct	1 ms	204 KB	Output is correct
33	Correct	1 ms	312 KB	Output is correct
34	Correct	1 ms	204 KB	Output is correct
35	Correct	1 ms	204 KB	Output is correct
36	Correct	1 ms	316 KB	Output is correct
37	Correct	1 ms	204 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct
39	Correct	71 ms	9084 KB	Output is correct
40	Correct	119 ms	14896 KB	Output is correct
41	Correct	56 ms	7364 KB	Output is correct
42	Correct	59 ms	6624 KB	Output is correct
43	Correct	40 ms	4696 KB	Output is correct
44	Correct	146 ms	18756 KB	Output is correct
45	Correct	141 ms	18664 KB	Output is correct
46	Correct	144 ms	18884 KB	Output is correct
47	Correct	129 ms	18800 KB	Output is correct
48	Correct	135 ms	18792 KB	Output is correct
49	Correct	575 ms	37340 KB	Output is correct
50	Correct	569 ms	37324 KB	Output is correct
51	Correct	577 ms	37460 KB	Output is correct
52	Correct	569 ms	37192 KB	Output is correct
53	Correct	558 ms	37288 KB	Output is correct
54	Correct	567 ms	37320 KB	Output is correct
55	Correct	1230 ms	65680 KB	Output is correct
56	Correct	1272 ms	65892 KB	Output is correct
57	Correct	1230 ms	65832 KB	Output is correct
58	Correct	1264 ms	65668 KB	Output is correct
59	Correct	1259 ms	65836 KB	Output is correct
60	Correct	1248 ms	65844 KB	Output is correct
61	Correct	1215 ms	65672 KB	Output is correct
62	Correct	1264 ms	65720 KB	Output is correct

Submission #405159

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 20.0 / 20.0

Subtask #4 55.0 / 55.0

Subtask #1
9.0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
20.0 / 20.0

Subtask #4
55.0 / 55.0