제출 #788145

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

constellation3

/* https://oj.uz/submission/286391 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int L = 20;
int n, m, a[N], x[N], y[N], c[N];
int logs[N], dfn[N], dfo[N], T, ls[N], rs[N];
pair<int, int> mx[N][L];
vector<int> ids[N];
ll dp[N];
pair<int, int> qmax(int l, int r) {
    int k = logs[r - l + 1];
    return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
void buildSparse() {
    for (int i = 2; i <= n; i++) {
        logs[i] = logs[i >> 1] + 1;
    }
    for (int i = 1; i <= n; i++) {
        mx[i][0] = make_pair(a[i], i);
    }
    for (int j = 1; j < L; j++) {
        for (int i = 1; i + (1 << j) <= n + 1; i++) {
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
        }
    }
}
void dfs(int &v, int tl, int tr) {
    if (tl + 1 >= tr) {
        v = 0;
        return;
    }
    v = qmax(tl + 1, tr - 1).second;
    dfs(ls[v], tl, v);
    dfs(rs[v], v, tr);
}
const int M = 8 * N;
ll sum[M];
void modify(int v, int tl, int tr, int ql, int qr, ll x) {
    if (tl > tr || tl > qr || tr < ql) {
        return;
    }
    if (ql <= tl && tr <= qr) {
        sum[v] += x;
        return;
    }
    int mid = tl + tr >> 1;
    modify(v * 2, tl, mid, ql, qr, x);
    modify(v * 2 + 1, mid + 1, tr, ql, qr, x);
}
ll query(int v, int tl, int tr, int qi) {
    if (tl == tr) {
        return sum[v];
    }
    int mid = tl + tr >> 1;
    if (qi <= mid) {
        return query(v * 2, tl, mid, qi) + sum[v];
    } else {
        return query(v * 2 + 1, mid + 1, tr, qi) + sum[v];
    }
}
void solve(int v) {
    if (!v) {
        return;
    }
    dfn[v] = ++T;
    solve(ls[v]);
    solve(rs[v]);
    dfo[v] = T;
    dp[v] = dp[ls[v]] + dp[rs[v]];
    for (int i : ids[v]) {
        dp[v] = max(dp[v], dp[ls[v]] + dp[rs[v]] + c[i] + query(1, 1, n, dfn[x[i]]));
    }
    modify(1, 1, n, dfn[v], dfo[v], dp[ls[v]] + dp[rs[v]] - dp[v]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    buildSparse();
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x[i], &y[i], &c[i]);
        int low = 1, high = x[i], from = 0, to = n + 1;
        while (low <= high) {
            int mid = low + high >> 1;
            if (qmax(mid, x[i]).first >= y[i]) {
                from = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        low = x[i], high = n;
        while (low <= high) {
            int mid = low + high >> 1;
            if (qmax(x[i], mid).first >= y[i]) {
                to = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        ids[qmax(from + 1, to - 1).second].push_back(i);
    }
    int root;
    dfs(root, 0, n + 1);
    solve(root);
    ll sum = 0;
    for (int i = 1; i <= m; i++) {
        sum += c[i];
    }
    printf("%lld\n", sum - dp[root]);
    return 0;
}

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

constellation3.cpp: In function 'void modify(int, int, int, int, int, long long int)':
constellation3.cpp:48:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
constellation3.cpp: In function 'long long int query(int, int, int, int)':
constellation3.cpp:56:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:88:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
constellation3.cpp:98:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
constellation3.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
constellation3.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
constellation3.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%d", &m);
      |     ~~~~~^~~~~~~~~~
constellation3.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d%d%d", &x[i], &y[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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