제출 #1003290

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

constellation3

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, maxN = 4e5 + 5, INF = 1e18;
struct range {
    int l, r;
    bool operator < (const range &b) const {
        if (r - l != b.r - b.l) return r - l < b.r - b.l;
        if (l != b.l) return l < b.l;
        return r < b.r;
    }
    bool operator == (const range &b) const {
        return (l == b.l && r == b.r);
    }
};
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;
    }
};
vector<node> star;
int dc1(node x) {return lower_bound(star.begin(), star.end(), x) - star.begin();}
vector<range> ranges;
int dc2(range x) {return lower_bound(ranges.begin(), ranges.end(), x) - ranges.begin();}

int sum[maxn];
vector<pair<int,int>> sub[maxn];
int ansR[maxn], ansS[maxN];
int worth(int x, int y, int R) {
    int val = sum[R];
    auto [l, r] = *prev(upper_bound(sub[R].begin(), sub[R].end(), make_pair(x, INF)));
    if (l <= x && x <= r) {
        int ID = dc2({l, r});
        val -= ansR[ID];
        val += worth(x, y, ID);
        // if (x == 5 && y == 8) cout << "test " << ansS[dc1({x, A[x]+1, 0})] << endl;
        // cout << "Test " << x << " " << A[x]+1 << " " << 0 << " " << ansS[dc1({x, A[x]+1, 0})] << endl;
    }
    return val;
}

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);
    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({a[i].second, a[i].first + 1, 0});
    
    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);
            ranges.push_back({*prev(it) + 1, *it - 1});
            // cout << "1 " << a[last].second << " " << ranges.back().first << " " << ranges.back().second << endl;
        }
        s.erase(a[i].second);
    }
    for (; last<=n; last++) {
        auto it = s.upper_bound(a[last].second);
        ranges.push_back({*prev(it) + 1, *it - 1});
        // cout << "2 " << a[last].second << " " << ranges.back().first << " " << ranges.back().second << endl;
    }
    sort(ranges.begin(), ranges.end()); ranges.erase(unique(ranges.begin(), ranges.end()), ranges.end());
    int sz = ranges.size();

    sort(star.begin(), star.end());
    vector<node> mem[sz];
    for (int i=0;i<sz;i++) sub[i] = {{0, 0}, {ranges[i].l, -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});
        if (c!=0) 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<sz;i++) {
        if (sub[i].back().first <= ranges[i].r) sub[i].back().second = ranges[i].r;
        else sub[i].pop_back();
        sub[i].push_back({INF, INF});
    }

    for (int i=0;i<sz;i++) {
        sum[i] = 0;
        for (auto [l, r]:sub[i]) {
            if (l!=0 && l!=INF) sum[i] += ansR[dc2({l, r})];
        }
        ansR[i] = sum[i];
        // cout << ranges[i].l << " " << ranges[i].r << " " << sum << endl;
        for (auto [x, y, c]:mem[i]) {
            int id = dc1({x, y, c});
            ansS[id] = worth(x, y, i) + c;
            ansR[i] = max(ansS[id], ansR[i]);
        }
    }
    cout << SUM - ansR[dc2({1, n})] << endl;
}

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

constellation3.cpp: In function 'int main()':
constellation3.cpp:50:9: warning: variable 'A' set but not used [-Wunused-but-set-variable]
   50 |     int A[n+1];
      |         ^

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