Submission #1270825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270825		hahahoang132	Constellation 3 (JOI20_constellation3)	C++20	0 / 100	1 ms	320 KiB

constellation3

//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e6 + 5;
const ll inf = LLONG_MAX/5;
const ll mod = 998244353;
#define bit(x,y) ((x >> y) & 1LL)
ll h[N];
struct haha
{
    ll x,y,c,id;
};
haha a[N];
ll cmp(haha x, haha y)
{
    return x.x < y.x;
}
ll cmp2(haha x, haha y)
{
    return x.x > y.x;
}
ll cmp3(haha x, haha y)
{
    return x.id < y.id;
}
ll d[N],d2[N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    ll i,j;
    for(i = 1;i <= n;i++)
    {
        cin >> h[i];
        h[i] = n - h[i];
    }
    ll m;
    cin >> m;
    ll s = 0;
    for(i = 1;i <= m;i++)
    {
        cin >> a[i].x >> a[i].y >> a[i].c;
        a[i].id = i;
        s += a[i].c;
        a[i].y = (n - a[i].y + 1);
    }
    sort(a + 1,a + 1 + m,cmp);
    priority_queue<pair<ll,ll>> pq;
    j = 0;
    ll ans = 0;
    for(i = 1;i <= n;i++)
    {
        while(!pq.empty() && pq.top().first > h[i])
        {
            d[0] = max(d[0],d[pq.top().second]);
            pq.pop();
        }
        while(j < m && a[j + 1].x <= i)
        {
            j++;
            d[a[j].id] = a[j].c + d[0];
            pq.push({a[j].y,a[j].id});
        }
    }
    sort(a + 1,a + 1 + m,cmp2);
    j = 0;
    while(!pq.empty()) pq.pop();
    for(i = n;i >= 1;i--)
    {
        while(!pq.empty() && pq.top().first > h[i])
        {
            d2[0] = max(d2[0],d2[pq.top().second]);
            pq.pop();
        }
        while(j < m && a[j + 1].x >= i)
        {
            j++;
            d2[a[j].id] = a[j].c + d2[0];
            pq.push({a[j].y,a[j].id});
        }
    }
    sort(a + 1,a + 1 + m,cmp3);
    ans = 0;
    for(i = 1;i <= m;i++) ans = max(ans,d[i] + d2[i] - a[i].c);
    cout << s - ans;
}

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