oj.uz

Submission #213449

# Submission time Handle Problem Language Result Execution time Memory
213449 2020-03-25T20:46:21 Z godwind Constellation 3 (JOI20_constellation3) C++14
100 / 100
 1444 ms 100072 KB 
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
// #include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;

#define int long long
#define y1 y11
#define less less228
#define left left228
#define right right228
#define list list228
#define all(v) v.begin(), v.end()
#define tm tm228
 
 
 
template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}

const int N = 228228;
const int LG = 20;

int n;
int a[N];
int stmax[N][LG], lg[N];

void pre() {
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1; i <= n; ++i) {
        stmax[i][0] = a[i];
    }
    for (int k = 1; (1 << k) <= n; ++k) {
        for (int i = 1; i <= n - (1 << k) + 1; ++i) {
            stmax[i][k] = max(stmax[i][k - 1], stmax[i + (1 << (k - 1))][k - 1]);
        }
    }
}
int getmax(int l, int r) {
    int k = lg[r - l + 1];
    return max(stmax[l][k], stmax[r - (1 << k) + 1][k]);
}
pair<int,int> get_segment(int x, int y) {
    int l = 0, r = x;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (getmax(mid, x) >= y) l = mid;
        else r = mid;
    }
    pair<int, int> ans = {r, 0};
    l = x, r = n + 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (getmax(x, mid) >= y) r = mid;
        else l = mid;
    }
    ans.second = l;
    return ans;
}
int forx[N];
vector<int> g[N], roots;
vector< pair<int, int> > in[N];
map< pair<int, int>, vector< pair<int,int> > > mp;
int take = 0;
int t[N], ss = 0;
void inc(int i, int dx) {
    for (; i < ss; i |= (i + 1)) {
        t[i] += dx;
    }
}
int gg = 0;
int get(int i) {
    gg = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1) {
        gg += t[i];
    }
    return gg;
}
void add(int l, int r, int x) {
    inc(l, x);
    inc(r + 1, -x);
}
int dp[N];
int tin[N], tout[N], timer = 0;
void dfs(int v) {
    int sums = 0;
    tin[v] = timer++;
    for (int to : g[v]) {
        dfs(to);
        sums += dp[to];
    }
    tout[v] = timer - 1;
    dp[v] = sums;
    for (pair<int, int> pa : in[v]) {
        int x = pa.first, cost = pa.second;
        int down = forx[x];
        if (down == -1 || down == v) {
            uax(dp[v], sums + cost);
        } else {
            uax(dp[v], sums + cost + get(tin[down]));
        }
    }
    int val = -dp[v] + sums;
    add(tin[v], tout[v], val);
}

vector<int> open[N], close[N];

void BuildTree() {
    vector< pair<int, int> > v;
    for (auto p : mp) {
        v.push_back(p.first);
    }
    int sz = (int)v.size();
    ss = sz + 3;
    sort(all(v), [&] (pair<int, int> a, pair<int, int> b) {
        return a.first < b.first || (a.first == b.first && a.second > b.second);
    });
    vector<int> left(sz, -1);
    vector<int> st;
    for (int i = sz - 1; i + 1; --i) {
        while (!st.empty() && v[st.back()].second <= v[i].second) {
            left[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    for (int i = 0; i < sz; ++i) {
        for (auto p : mp[v[i]]) {
            in[i].push_back(p);
        }
    }
    for (int i = 0; i < sz; ++i) {
        if (left[i] != -1) g[left[i]].push_back(i);
        else roots.push_back(i);
    }

    for (int i = 1; i <= n; ++i) {
        forx[i] = -1;
    }
    for (int i = 0; i < sz; ++i) {
        open[v[i].first].push_back(i);
        close[v[i].second + 1].push_back(i);
    }
    set<int> S;
    for (int x = 1; x <= n; ++x) {
        for (int i : open[x]) {
            S.insert(i);
        }
        for (int i : close[x]) {
            S.erase(i);
        }
        if (!S.empty()) forx[x] = *S.rbegin();
        else forx[x] = -1;
    }
    for (int i : roots) {
        dfs(i);
        take += dp[i];
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    pre();
    int m;
    cin >> m;
    int all = 0;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        all += c;
        pair<int, int> pa = get_segment(x, y);
        mp[pa].push_back(make_pair(x, c));
    }
    BuildTree();
    cout << all - take << '\n';
    return 0;
}
// RU_023
 
/*
5
1 3 4 2 3
3
1 5 3
4 3 2
2 4 2

 
7
5 6 2 3 6 7 6
5
7 7 5
3 3 7
3 7 10
1 7 6
4 7 8


8
6 8 5 7 3 4 2 1
10
8 2 9
6 6 7
8 3 18
5 8 17
8 5 3
5 5 3
5 4 8
1 8 13
1 7 5
7 4 13

 
 
*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22016 KB Output is correct
2 Correct 19 ms 22016 KB Output is correct
3 Correct 18 ms 21760 KB Output is correct
4 Correct 19 ms 22016 KB Output is correct
5 Correct 19 ms 22016 KB Output is correct
6 Correct 18 ms 22016 KB Output is correct
7 Correct 20 ms 22016 KB Output is correct
8 Correct 18 ms 22016 KB Output is correct
9 Correct 19 ms 22016 KB Output is correct
10 Correct 18 ms 22016 KB Output is correct
11 Correct 18 ms 22016 KB Output is correct
12 Correct 18 ms 22016 KB Output is correct
13 Correct 18 ms 22016 KB Output is correct
14 Correct 17 ms 21888 KB Output is correct
15 Correct 18 ms 21888 KB Output is correct
16 Correct 18 ms 22016 KB Output is correct
17 Correct 18 ms 21888 KB Output is correct
18 Correct 18 ms 22016 KB Output is correct
19 Correct 18 ms 21888 KB Output is correct
20 Correct 19 ms 22016 KB Output is correct
21 Correct 18 ms 22016 KB Output is correct
22 Correct 18 ms 21888 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22016 KB Output is correct
2 Correct 19 ms 22016 KB Output is correct
3 Correct 18 ms 21760 KB Output is correct
4 Correct 19 ms 22016 KB Output is correct
5 Correct 19 ms 22016 KB Output is correct
6 Correct 18 ms 22016 KB Output is correct
7 Correct 20 ms 22016 KB Output is correct
8 Correct 18 ms 22016 KB Output is correct
9 Correct 19 ms 22016 KB Output is correct
10 Correct 18 ms 22016 KB Output is correct
11 Correct 18 ms 22016 KB Output is correct
12 Correct 18 ms 22016 KB Output is correct
13 Correct 18 ms 22016 KB Output is correct
14 Correct 17 ms 21888 KB Output is correct
15 Correct 18 ms 21888 KB Output is correct
16 Correct 18 ms 22016 KB Output is correct
17 Correct 18 ms 21888 KB Output is correct
18 Correct 18 ms 22016 KB Output is correct
19 Correct 18 ms 21888 KB Output is correct
20 Correct 19 ms 22016 KB Output is correct
21 Correct 18 ms 22016 KB Output is correct
22 Correct 18 ms 21888 KB Output is correct
23 Correct 21 ms 22400 KB Output is correct
24 Correct 20 ms 22528 KB Output is correct
25 Correct 20 ms 22528 KB Output is correct
26 Correct 22 ms 22528 KB Output is correct
27 Correct 22 ms 22528 KB Output is correct
28 Correct 20 ms 22528 KB Output is correct
29 Correct 21 ms 22528 KB Output is correct
30 Correct 20 ms 22656 KB Output is correct
31 Correct 22 ms 22528 KB Output is correct
32 Correct 21 ms 22528 KB Output is correct
33 Correct 21 ms 22400 KB Output is correct
34 Correct 20 ms 22528 KB Output is correct
35 Correct 20 ms 22528 KB Output is correct
36 Correct 20 ms 22272 KB Output is correct
37 Correct 19 ms 22272 KB Output is correct
38 Correct 20 ms 22656 KB Output is correct
39 Correct 20 ms 22400 KB Output is correct
40 Correct 20 ms 22528 KB Output is correct
41 Correct 20 ms 22400 KB Output is correct
42 Correct 21 ms 22400 KB Output is correct
43 Correct 20 ms 22400 KB Output is correct
44 Correct 20 ms 22400 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22016 KB Output is correct
2 Correct 19 ms 22016 KB Output is correct
3 Correct 18 ms 21760 KB Output is correct
4 Correct 19 ms 22016 KB Output is correct
5 Correct 19 ms 22016 KB Output is correct
6 Correct 18 ms 22016 KB Output is correct
7 Correct 20 ms 22016 KB Output is correct
8 Correct 18 ms 22016 KB Output is correct
9 Correct 19 ms 22016 KB Output is correct
10 Correct 18 ms 22016 KB Output is correct
11 Correct 18 ms 22016 KB Output is correct
12 Correct 18 ms 22016 KB Output is correct
13 Correct 18 ms 22016 KB Output is correct
14 Correct 17 ms 21888 KB Output is correct
15 Correct 18 ms 21888 KB Output is correct
16 Correct 18 ms 22016 KB Output is correct
17 Correct 18 ms 21888 KB Output is correct
18 Correct 18 ms 22016 KB Output is correct
19 Correct 18 ms 21888 KB Output is correct
20 Correct 19 ms 22016 KB Output is correct
21 Correct 18 ms 22016 KB Output is correct
22 Correct 18 ms 21888 KB Output is correct
23 Correct 21 ms 22400 KB Output is correct
24 Correct 20 ms 22528 KB Output is correct
25 Correct 20 ms 22528 KB Output is correct
26 Correct 22 ms 22528 KB Output is correct
27 Correct 22 ms 22528 KB Output is correct
28 Correct 20 ms 22528 KB Output is correct
29 Correct 21 ms 22528 KB Output is correct
30 Correct 20 ms 22656 KB Output is correct
31 Correct 22 ms 22528 KB Output is correct
32 Correct 21 ms 22528 KB Output is correct
33 Correct 21 ms 22400 KB Output is correct
34 Correct 20 ms 22528 KB Output is correct
35 Correct 20 ms 22528 KB Output is correct
36 Correct 20 ms 22272 KB Output is correct
37 Correct 19 ms 22272 KB Output is correct
38 Correct 20 ms 22656 KB Output is correct
39 Correct 20 ms 22400 KB Output is correct
40 Correct 20 ms 22528 KB Output is correct
41 Correct 20 ms 22400 KB Output is correct
42 Correct 21 ms 22400 KB Output is correct
43 Correct 20 ms 22400 KB Output is correct
44 Correct 20 ms 22400 KB Output is correct
45 Correct 1444 ms 85352 KB Output is correct
46 Correct 1055 ms 84452 KB Output is correct
47 Correct 1116 ms 84332 KB Output is correct
48 Correct 1089 ms 85096 KB Output is correct
49 Correct 1069 ms 83564 KB Output is correct
50 Correct 1057 ms 83176 KB Output is correct
51 Correct 1092 ms 83812 KB Output is correct
52 Correct 1103 ms 84972 KB Output is correct
53 Correct 1440 ms 84584 KB Output is correct
54 Correct 1107 ms 92904 KB Output is correct
55 Correct 1123 ms 87020 KB Output is correct
56 Correct 1081 ms 83304 KB Output is correct
57 Correct 1072 ms 80616 KB Output is correct
58 Correct 862 ms 65144 KB Output is correct
59 Correct 849 ms 64760 KB Output is correct
60 Correct 485 ms 100072 KB Output is correct
61 Correct 935 ms 73672 KB Output is correct
62 Correct 1140 ms 91880 KB Output is correct
63 Correct 932 ms 72380 KB Output is correct
64 Correct 909 ms 71884 KB Output is correct
65 Correct 1119 ms 92136 KB Output is correct
66 Correct 919 ms 71288 KB Output is correct