제출 #888637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888637		Pring	별자리 3 (JOI20_constellation3)	C++14	100 / 100	349 ms	68392 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
typedef long long ll;
typedef pair<int, int> pii;

const int MXN = 200005;
int n, m, a[MXN], px[MXN], py[MXN], pc[MXN];
vector<int> v[MXN];

struct SMG {
    int val[MXN * 4];
    void build(int id, int l, int r) {
        if (l + 1 == r) {
            val[id] = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(id * 2 + 1, l, mid);
        build(id * 2 + 2, mid, r);
        val[id] = (a[val[id * 2 + 1]] >= a[val[id * 2 + 2]] ? val[id * 2 + 1] : val[id * 2 + 2]);
    }
    int query(int id, int l, int r, int _l, int _r) {
        if (_r <= l || r <= _l) return 0;
        if (_l <= l && r <= _r) return val[id];
        int mid = (l + r) >> 1;
        int vl = query(id * 2 + 1, l, mid, _l, _r), vr = query(id * 2 + 2, mid, r, _l, _r);
        return (a[vl] >= a[vr] ? vl : vr);
    }
    void DFS(int id, int l, int r) {
        debug(l, r, val[id]);
        if (l + 1 == r) return;
        int mid = (l + r) >> 1;
        DFS(id * 2 + 1, l, mid);
        DFS(id * 2 + 2, mid, r);
    }
} smg;

struct BIT {
    int n, val[MXN];
    void init(int _n) {
        n = _n;
        fill(val + 1, val + n + 1, 0);
    }
    void modify(int id, int v) {
        for (; id <= n; id += (id & -id)) val[id] += v;
    }
    int query(int id) {
        int ans = 0;
        for (; id > 0; id -= (id & -id)) ans += val[id];
        return ans;
    }
} B;

namespace CT {
    int rt, flc = 1;
    pii ct[MXN], fl[MXN];
    // int pos[MXN];

    int build(int l, int r) {
        if (l >= r) return -1;
        int rt = smg.query(0, 0, n + 1, l, r);
        ct[rt].fs = build(l, rt);
        ct[rt].sc = build(rt + 1, r);
        return rt;
    }

    void FLAT(int id) {
        fl[id].fs = flc++;
        if (ct[id].fs != -1) FLAT(ct[id].fs);
        if (ct[id].sc != -1) FLAT(ct[id].sc);
        fl[id].sc = flc;
    }

    void DFS(int id, ll &x) {
        if (ct[id].fs != -1) DFS(ct[id].fs, x);
        if (ct[id].sc != -1) DFS(ct[id].sc, x);
        int ans = 0;
        for (auto &i : v[id]) {
            // debug(pc[i], px[i], B.query(fl[px[i]].fs));
            int now = pc[i];
            now -= B.query(fl[px[i]].fs);
            ans = max(ans, now);
        }
        debug(id, ans);
        // debug(fl[id].fs, fl[id].sc);
        x -= ans;
        B.modify(fl[id].fs, ans);
        B.modify(fl[id].sc, -ans);
        // FOR(i, 1, n + 1) cout << B.val[i] << ' ';
        // cout << endl;
    }
}

namespace PUT {
    set<int> S;
    vector<pii> op;

    void DO() {
        S.insert(0);
        S.insert(n + 1);
        FOR(i, 1, n + 1) op.push_back(mp(a[i], i));
        FOR(i, 1, m + 1) op.push_back(mp(py[i], -i));
        sort(op.begin(), op.end(), greater<pii>());
        for (auto &i : op) {
            int id = abs(i.sc);
            if (i.sc > 0) S.insert(id);
            else {
                auto itr = S.upper_bound(px[id]);
                auto itl = prev(itr);
                v[smg.query(0, 0, n + 1, *itl + 1, *itr)].push_back(id);
            }
        }
    }
}

void miku() {
    cin >> n;
    FOR(i, 1, n + 1) cin >> a[i];
    cin >> m;
    FOR(i, 1, m + 1) cin >> px[i] >> py[i] >> pc[i];
    smg.build(0, 0, n + 1);
    CT::rt = smg.query(0, 0, n + 1, 1, n + 1);
    CT::build(1, n + 1);
    CT::FLAT(CT::rt);
    // FOR(i, 1, n + 1) debug(CT::fl[i].fs, CT::fl[i].sc);
    PUT::DO();
    // return;
    B.init(n);
    ll ans = 0;
    CT::DFS(CT::rt, ans);
    FOR(i, 1, m + 1) ans += pc[i];
    // FOR(i, 1, n + 1) ans -= B.query(i);
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    miku();
    return 0;
}

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

constellation3.cpp: In member function 'void SMG::DFS(long long int, long long int, long long int)':
constellation3.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
constellation3.cpp:45:9: note: in expansion of macro 'debug'
   45 |         debug(l, r, val[id]);
      |         ^~~~~
constellation3.cpp: In function 'void CT::DFS(long long int, ll&)':
constellation3.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
constellation3.cpp:99:9: note: in expansion of macro 'debug'
   99 |         debug(id, ans);
      |         ^~~~~
constellation3.cpp: In function 'void PUT::DO()':
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:116:9: note: in expansion of macro 'FOR'
  116 |         FOR(i, 1, n + 1) op.push_back(mp(a[i], i));
      |         ^~~
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:117:9: note: in expansion of macro 'FOR'
  117 |         FOR(i, 1, m + 1) op.push_back(mp(py[i], -i));
      |         ^~~
constellation3.cpp: In function 'void miku()':
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:133:5: note: in expansion of macro 'FOR'
  133 |     FOR(i, 1, n + 1) cin >> a[i];
      |     ^~~
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:135:5: note: in expansion of macro 'FOR'
  135 |     FOR(i, 1, m + 1) cin >> px[i] >> py[i] >> pc[i];
      |     ^~~
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:146:5: note: in expansion of macro 'FOR'
  146 |     FOR(i, 1, m + 1) ans += pc[i];
      |     ^~~

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