Submission #217830

#	Time	Username	Problem	Language	Result	Execution time	Memory
217830		Hideo	Constellation 3 (JOI20_constellation3)	C++11	0 / 100	18 ms	23808 KiB

constellation3

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

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

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define pii pair < int, pi >
#define next next123
#define left left123

const int N = 2e5 + 7;
const ll INF = 1e18 + 7;

struct point{
    int x, y, c;
} b[2 * N];

ll dp[N], g[8 * N];
int t[8 * N];
int a[N], next[N];
int n, m;

bool comp (point a, point b){
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

void build (int v, int l, int r){
    if (l == r)
        t[v] = a[l];
    else {
        int mid = (l + r) >> 1;
        build(v + v, l, mid);
        build(v + v + 1, mid + 1, r);
        t[v] = max(t[v + v], t[v + v + 1]);
    }
}

int get (int v, int l, int r, int ql, int qr){
    if (ql <= l && r <= qr)
        return t[v];
    if (r < ql || qr < l)
        return 0;
    int mid = (l + r) >> 1;
    return max(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
}

void upd (int v, int l, int r, int pos, ll val){
    if (l == r)
        g[v] = min(val, g[v]);
    else {
        int mid = (l + r) >> 1;
        if (pos <= mid)
            upd(v + v, l, mid, pos, val);
        else
            upd(v + v + 1, mid + 1, r, pos, val);
        g[v] = g[v + v] + g[v + v + 1];
    }
}

ll get2 (int v, int l, int r, int ql, int qr){
    if (ql <= l && r <= qr)
        return g[v];
    if (r < ql || qr < l)
        return 0LL;
    int mid = (l + r) >> 1;
    return get2(v + v, l, mid, ql, qr) + get2(v + v + 1, mid + 1, r, ql, qr);
}

vi event[N];
vector < ll > cost[N];

main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        b[i] = {i, 0, 0};
    }
    cin >> m;
    m += n;
    build(1, 1, n);
    for (int i = n + 1; i <= m; i++)
        scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].c);
    sort(b + 1, b + m + 1, comp);
    int l = 1;
    ll s = 0;
    for (int i = 1; i <= m; i++){
        s += b[i].c;
        if (b[i].x != b[i + 1].x){
            for (l; l <= i; l++){
                ll tmp;
                if (cost[b[l].x].size())
                    tmp = cost[b[l].x].back();
                else
                    tmp = INF;
                cost[b[l].x].pb(min(s - b[l].c, tmp));
                if (!b[l].y){
                    event[1].pb(b[l].x);
                    continue;
                }
                int ml = b[l].x, mr = n + 1;
                while (ml + 1 < mr){
                    int mid = (ml + mr) >> 1;
                    if (get(1, 1, n, b[l].x, mid) >= b[l].y)
                        mr = mid;
                    else
                        ml = mid;
                }
                event[mr].pb(b[l].x);
            }
            l = i + 1;
            s = 0;
        }
    }
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    memset(g, 0x3f3f3f3f, sizeof(g));
    dp[0] = 0;
    int cur = 1;
    for (int i = 1; i <= n; i++){
        for (int it : event[i]){
            upd(1, 1, n, it, cost[it][next[it]]);
            next[it]++;
        }
        int cnt = 0;
        for (cur; cur <= m && b[cur].x == i; cur++){
            int l = 0, r = i;
            while (l + 1 < r){
                int mid = (l + r) >> 1;
                if (get(1, 1, n, mid, i) >= b[cur].y)
                    l = mid;
                else
                    r = mid;
            }
            ll res = dp[l] + cost[i][cnt];
            if (l + 1 <= i - 1)
                res += get2(1, 1, n, l + 1, i - 1);
            dp[i] = min(dp[i], res);
            cnt++;
        }
        while (b[cur].x == i || b[cur - 1].x != i);
    }
    cout << dp[n];
}

Compilation message (stderr)

constellation3.cpp:83:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
constellation3.cpp: In function 'int main()':
constellation3.cpp:100:19: warning: statement has no effect [-Wunused-value]
             for (l; l <= i; l++){
                   ^
constellation3.cpp:135:17: warning: statement has no effect [-Wunused-value]
         for (cur; cur <= m && b[cur].x == i; cur++){
                 ^
constellation3.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
constellation3.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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