oj.uz

Submission #430148

# Submission time Handle Problem Language Result Execution time Memory
430148 2021-06-16T11:42:36 Z 2qbingxuan Constellation 3 (JOI20_constellation3) C++14
100 / 100
 549 ms 58696 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define pary(a...) danb(#a, a)
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\033[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\033[0m\n";
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define pb emplace_back

using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
const int mod = 1000000007;
const int inf = 1e9;
const ll INF = 1e18;
const int maxn = 200025;

void chmax(ll &x, ll v) {
    if (x < v) x = v;
}
bool alive[maxn];

int pa[maxn];
int anc(int x) { return x==pa[x] ? x : pa[x]=anc(pa[x]); }
map<int,ll> top[maxn];
ll tag[maxn];
ll dp[maxn];
void join(int a, int b, int h) {
    a = anc(a);
    b = anc(b);
    assert (a != b);
    while (top[a].size() && top[a].begin()->first <= h) {
        chmax(dp[a], top[a].begin()->second + tag[a]);
        top[a].erase(top[a].begin());
    }
    while (top[b].size() && top[b].begin()->first <= h) {
        chmax(dp[b], top[b].begin()->second + tag[b]);
        top[b].erase(top[b].begin());
    }
    ll tmpdp = dp[b] + dp[a];
    tag[a] += dp[b];
    tag[b] += dp[a];
    if (top[a].size() > top[b].size()) {
        for (auto [y, val]: top[b])
            chmax(top[a][y], val + tag[b] - tag[a]);
        swap(top[a], top[b]);
        swap(tag[a], tag[b]);
    } else {
        for (auto [y, val]: top[a])
            chmax(top[b][y], val + tag[a] - tag[b]);
    }
    dp[b] = tmpdp;
    pa[a] = b;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    iota(pa, pa+n, 0);
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    int m;
    cin >> m;
    ll tot = 0, ans = 0;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        --x;
        chmax(top[x][y], c);
        tot += c;
    }
    map<int, vector<int>> mp;
    for (int i = 0; i < n; i++) mp[A[i]].push_back(i);
    for (const auto &[h, indices]: mp) {
        for (int i: indices) {
            if (i > 0 && alive[i-1]) {
                join(i-1, i, h);
            }
            if (i+1 < n && alive[i+1]) {
                join(i, i+1, h);
            }
            alive[i] = true;
        }
    }
    int root = anc(0);
    for (auto [y, val]: top[root]) chmax(ans, val + tag[root]);
    chmax(ans, dp[root]);
    cout << tot - ans << '\n';
}

Compilation message

constellation3.cpp: In function 'void join(int, int, int)':
constellation3.cpp:61:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         for (auto [y, val]: top[b])
      |                   ^
constellation3.cpp:66:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |         for (auto [y, val]: top[a])
      |                   ^
constellation3.cpp: In function 'int main()':
constellation3.cpp:93:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |     for (const auto &[h, indices]: mp) {
      |                      ^
constellation3.cpp:105:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |     for (auto [y, val]: top[root]) chmax(ans, val + tag[root]);
      |               ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 9 ms 9676 KB Output is correct
3 Correct 8 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 7 ms 9732 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 8 ms 9676 KB Output is correct
10 Correct 8 ms 9728 KB Output is correct
11 Correct 8 ms 9732 KB Output is correct
12 Correct 8 ms 9804 KB Output is correct
13 Correct 9 ms 9728 KB Output is correct
14 Correct 7 ms 9720 KB Output is correct
15 Correct 7 ms 9676 KB Output is correct
16 Correct 7 ms 9676 KB Output is correct
17 Correct 8 ms 9676 KB Output is correct
18 Correct 8 ms 9772 KB Output is correct
19 Correct 7 ms 9676 KB Output is correct
20 Correct 7 ms 9676 KB Output is correct
21 Correct 7 ms 9676 KB Output is correct
22 Correct 8 ms 9676 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 9 ms 9676 KB Output is correct
3 Correct 8 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 7 ms 9732 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 8 ms 9676 KB Output is correct
10 Correct 8 ms 9728 KB Output is correct
11 Correct 8 ms 9732 KB Output is correct
12 Correct 8 ms 9804 KB Output is correct
13 Correct 9 ms 9728 KB Output is correct
14 Correct 7 ms 9720 KB Output is correct
15 Correct 7 ms 9676 KB Output is correct
16 Correct 7 ms 9676 KB Output is correct
17 Correct 8 ms 9676 KB Output is correct
18 Correct 8 ms 9772 KB Output is correct
19 Correct 7 ms 9676 KB Output is correct
20 Correct 7 ms 9676 KB Output is correct
21 Correct 7 ms 9676 KB Output is correct
22 Correct 8 ms 9676 KB Output is correct
23 Correct 9 ms 9992 KB Output is correct
24 Correct 9 ms 10060 KB Output is correct
25 Correct 10 ms 9976 KB Output is correct
26 Correct 9 ms 10020 KB Output is correct
27 Correct 9 ms 9992 KB Output is correct
28 Correct 10 ms 10060 KB Output is correct
29 Correct 11 ms 10060 KB Output is correct
30 Correct 10 ms 10060 KB Output is correct
31 Correct 10 ms 10060 KB Output is correct
32 Correct 10 ms 10188 KB Output is correct
33 Correct 9 ms 10108 KB Output is correct
34 Correct 9 ms 10120 KB Output is correct
35 Correct 11 ms 10188 KB Output is correct
36 Correct 9 ms 9996 KB Output is correct
37 Correct 9 ms 9932 KB Output is correct
38 Correct 9 ms 10060 KB Output is correct
39 Correct 9 ms 9932 KB Output is correct
40 Correct 9 ms 10060 KB Output is correct
41 Correct 8 ms 9932 KB Output is correct
42 Correct 9 ms 9932 KB Output is correct
43 Correct 9 ms 10108 KB Output is correct
44 Correct 9 ms 9972 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 9 ms 9676 KB Output is correct
3 Correct 8 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 7 ms 9732 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 8 ms 9676 KB Output is correct
10 Correct 8 ms 9728 KB Output is correct
11 Correct 8 ms 9732 KB Output is correct
12 Correct 8 ms 9804 KB Output is correct
13 Correct 9 ms 9728 KB Output is correct
14 Correct 7 ms 9720 KB Output is correct
15 Correct 7 ms 9676 KB Output is correct
16 Correct 7 ms 9676 KB Output is correct
17 Correct 8 ms 9676 KB Output is correct
18 Correct 8 ms 9772 KB Output is correct
19 Correct 7 ms 9676 KB Output is correct
20 Correct 7 ms 9676 KB Output is correct
21 Correct 7 ms 9676 KB Output is correct
22 Correct 8 ms 9676 KB Output is correct
23 Correct 9 ms 9992 KB Output is correct
24 Correct 9 ms 10060 KB Output is correct
25 Correct 10 ms 9976 KB Output is correct
26 Correct 9 ms 10020 KB Output is correct
27 Correct 9 ms 9992 KB Output is correct
28 Correct 10 ms 10060 KB Output is correct
29 Correct 11 ms 10060 KB Output is correct
30 Correct 10 ms 10060 KB Output is correct
31 Correct 10 ms 10060 KB Output is correct
32 Correct 10 ms 10188 KB Output is correct
33 Correct 9 ms 10108 KB Output is correct
34 Correct 9 ms 10120 KB Output is correct
35 Correct 11 ms 10188 KB Output is correct
36 Correct 9 ms 9996 KB Output is correct
37 Correct 9 ms 9932 KB Output is correct
38 Correct 9 ms 10060 KB Output is correct
39 Correct 9 ms 9932 KB Output is correct
40 Correct 9 ms 10060 KB Output is correct
41 Correct 8 ms 9932 KB Output is correct
42 Correct 9 ms 9932 KB Output is correct
43 Correct 9 ms 10108 KB Output is correct
44 Correct 9 ms 9972 KB Output is correct
45 Correct 508 ms 47508 KB Output is correct
46 Correct 515 ms 47044 KB Output is correct
47 Correct 549 ms 47556 KB Output is correct
48 Correct 485 ms 47240 KB Output is correct
49 Correct 476 ms 46900 KB Output is correct
50 Correct 474 ms 46452 KB Output is correct
51 Correct 526 ms 46996 KB Output is correct
52 Correct 497 ms 47736 KB Output is correct
53 Correct 504 ms 47144 KB Output is correct
54 Correct 417 ms 58056 KB Output is correct
55 Correct 380 ms 58068 KB Output is correct
56 Correct 398 ms 58076 KB Output is correct
57 Correct 488 ms 58696 KB Output is correct
58 Correct 356 ms 39632 KB Output is correct
59 Correct 377 ms 39880 KB Output is correct
60 Correct 183 ms 55876 KB Output is correct
61 Correct 287 ms 39040 KB Output is correct
62 Correct 357 ms 49368 KB Output is correct
63 Correct 283 ms 36476 KB Output is correct
64 Correct 290 ms 38440 KB Output is correct
65 Correct 345 ms 49252 KB Output is correct
66 Correct 263 ms 37312 KB Output is correct