제출 #1003463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003463		onbert	별자리 3 (JOI20_constellation3)	C++17	100 / 100	802 ms	126436 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 6e5 + 5;
struct node {
    int x, y, c;
    bool operator < (const node &b) const {
        if (y!=b.y) return y < b.y;
        if (x!=b.x) return x < b.x;
        return c < b.c;
    }
};

int siz;
int fen[maxn];
void update(int id, int val) {
    while (id <= siz) {
        fen[id] += val;
        id += (id & -id);
    }
}
int qry(int id) {
    int val = 0;
    while (id>=1) {
        val += fen[id];
        id -= (id & -id);
    }
    return val;
}

vector<node> star;
int dc1(node x) {return lower_bound(star.begin(), star.end(), x) - star.begin();}
vector<pair<int,int>> ranges;
int dc2(pair<int,int> x) {return lower_bound(ranges.begin(), ranges.end(), x) - ranges.begin();}
pair<int,int> in[maxn];
vector<node> mem[maxn];

vector<int> ADJ[maxn];
int sz[maxn], d[maxn], newid[maxn], lim[maxn], nxt[maxn], fa[maxn], cnter = 0;
void dfs1(int u) {
    sz[u] = 1;
    for (int v:ADJ[u]) {
        dfs1(v);
        sz[u] += sz[v];
    }
    for (int i=1;i<ADJ[u].size();i++) if (sz[ADJ[u][i]] > sz[ADJ[u][0]]) swap(ADJ[u][i], ADJ[u][0]);
}
void dfs2(int u) {
    cnter++;
    newid[u] = cnter;
    // cout << u << " " << ranges[u].first << " " << ranges[u].second << endl;
    for (int v:ADJ[u]) {
        // cout << u << " " << v << endl;
        d[cnter+1] = d[newid[u]] + 1;
        fa[cnter+1] = newid[u];
        if (v == ADJ[u][0]) nxt[cnter+1] = nxt[newid[u]];
        else nxt[cnter+1] = cnter+1;
        dfs2(v);
    }
    lim[newid[u]] = cnter;
}

int PATH(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    vector<pair<int,int>> path;
    if (u!=v) {
        path = {{nxt[u], u}};
        u = nxt[u];
        while (u > v || v > lim[u]) {
            u = fa[u];
            path.push_back({nxt[u], u});
            u = nxt[u];
        }
        auto [l, r] = path.back();
        while (l<r) {
            int mid = (l+r+1)/2;
            if (mid<=v && v<=lim[mid]) l = mid;
            else r = mid-1;
        }
        path.back().first = u = l;
        path.push_back({nxt[v], v});
        v = nxt[v];
        while (d[fa[v]] > d[u]) {
            v = fa[v];
            path.push_back({nxt[v], v});
            v = nxt[v];
        }
        path.back().first += d[u] - d[v] + 1;
    } else path = {{u, u}};

    int val = 0;
    for (auto [L, R]:path) val += qry(R) - qry(L-1);
    // cout << val << endl;
    return val;
}


int ansR[maxn], ansS[maxn];
void dfs3(int u) {
    for (int v:ADJ[u]) dfs3(v);
    ansR[u] = 0;
    // cout << "RANGE " << u << " " << ranges[u].first << " " << ranges[u].second << endl;
    for (auto [x, y, c]:mem[u]) {
        // cout << x << " " << y << " " << c << endl;
        int id = dc1({x, y, c}), end = dc2(in[x]);
        // cout << "end " << " " << end << " " << in[x].first << " " << in[x].second << endl;
        ansS[id] = PATH(newid[u], newid[end]) + c;
        ansR[u] = max(ansS[id], ansR[u]);
        // cout << ansS[id] << endl;
    }
    update(newid[u], -ansR[u]);
    if (fa[newid[u]] != -1) update(fa[newid[u]], ansR[u]);
}


signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    pair<int,int> a[n+1];
    int A[n+1];
    for (int i=1;i<=n;i++) {
        cin >> a[i].first;
        a[i].second = i;
        A[i] = a[i].first;
    }
    sort(a+1, a+n+1);
    set<int> s;
    for (int i=0;i<=n+1;i++) s.insert(i);
    int last = 1;
    for (int i=1;i<=n;i++) {
        for (; a[last].first < a[i].first; last++) {
            auto it = s.upper_bound(a[last].second);
            pair<int,int> cur = {*prev(it) + 1, *it - 1};
            ranges.push_back(cur);
            in[a[last].second] = cur;
            // cout << "bruh " << a[last].second << " " << cur.first << " " << cur.second << endl;
        }
        s.erase(a[i].second);
    }
    for (; last<=n; last++) {
        auto it = s.upper_bound(a[last].second);
        pair<int,int> cur = {*prev(it) + 1, *it - 1};
        ranges.push_back(cur);
        in[a[last].second] = cur;
        // cout << "bruh " << a[last].second << " " << cur.first << " " << cur.second << endl;
    }
    sort(ranges.begin(), ranges.end()); ranges.erase(unique(ranges.begin(), ranges.end()), ranges.end());


    int m, SUM = 0;
    cin >> m;
    for (int i=1;i<=m;i++) {
        int x, y, c;
        cin >> x >> y >> c;
        star.push_back({x, y, c});
        SUM += c;
    }
    for (int i=1;i<=n;i++) star.push_back({i, A[i]+1, 0});
    
    siz = ranges.size();

    sort(star.begin(), star.end());
    vector<pair<int,int>> sub[siz];
    for (int i=0;i<siz;i++) sub[i] = {{ranges[i].first, -1}};
    for (int i=1;i<=n;i++) s.insert(i);
    last = 1;
    for (auto [x, y, c]:star) {
        // cout << x << " " << y << " " << c << endl;
        for (;last <= n && a[last].first < y; last++) s.erase(a[last].second);
        auto it = s.lower_bound(x);
        int l = *prev(it) + 1, r = *it - 1;
        int id = dc2({l, r});
        mem[id].push_back({x, y, c});
        // cout << id << endl;
        if (c==0) {
            if (x-1>=sub[id].back().first) {
                sub[id].back().second = x-1;
                sub[id].push_back({x+1, -1});
            } else sub[id].back().first = x+1;
        }
    }

    for (int i=0;i<siz;i++) {
        if (sub[i].back().first <= ranges[i].second) sub[i].back().second = ranges[i].second;
        else sub[i].pop_back();
        for (auto [l, r]:sub[i]) ADJ[i].push_back(dc2({l, r}));
    }
    int first = dc2({1, n});
    d[1] = 0, nxt[1] = 1, fa[1] = -1;
    dfs1(first); dfs2(first);
    dfs3(first);
    // for (int i=1;i<=n;i++) cout << nxt[i] << " "; cout << endl;

    cout << SUM - ansR[first] << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'void dfs1(long long int)':
constellation3.cpp:46:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i=1;i<ADJ[u].size();i++) if (sz[ADJ[u][i]] > sz[ADJ[u][0]]) swap(ADJ[u][i], ADJ[u][0]);
      |                  ~^~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65