Submission #330370

#	Time	Username	Problem	Language	Result	Execution time	Memory
330370		limabeans	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	547 ms	43500 KiB

constellation3

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 2e5 + 10;


int n;
ll a[maxn];

int m;
vector<pair<pair<ll,ll>,ll>> stars; //((y,x),c)
vector<int> byX[maxn];

int pre[maxn], nex[maxn];


struct segtree {
    int n;
    vector<ll> t, o;
    void init(int _n) {
	n=_n+10;
	t.assign(4*n,0);
	o.assign(4*n,0);
    }

    void push(int v, int tl, int tr) {
	if (!o[v]) return;
	int tm=(tl+tr)/2;
	t[2*v] += 1ll*(tm-tl+1)*o[v];
	t[2*v+1] += 1ll*(tr-tm)*o[v];
	o[2*v] += o[v];
	o[2*v+1] += o[v];
	o[v] = 0;
    }

    ll qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) return 0;
	if (l<=tl && tr<=r) return t[v];
	push(v,tl,tr);
	int tm=(tl+tr)/2;
	return qry(2*v,tl,tm,l,r)+qry(2*v+1,tm+1,tr,l,r);
    }

    void upd(int v, int tl, int tr, int l, int r, ll dx) {
	if (l>tr || r<tl) return;
	if (l<=tl && tr<=r) {
	    t[v] += 1ll*(tr-tl+1)*dx;
	    o[v] += dx;
	} else {
	    push(v,tl,tr);
	    int tm=(tl+tr)/2;
	    upd(2*v,tl,tm,l,r,dx);
	    upd(2*v+1,tm+1,tr,l,r,dx);
	    t[v]=t[2*v]+t[2*v+1];
	}
    }
};



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
	a[i]=n-a[i];
    }


    ll sum = 0;

    cin>>m;
    stars.resize(m);
    for (int i=0; i<m; i++) {
	cin>>stars[i].first.second>>stars[i].first.first>>stars[i].second;
	stars[i].first.first = n-stars[i].first.first+1;
	
	sum += stars[i].second;
    }

    sort(stars.rbegin(),stars.rend());

    for (int i=0; i<m; i++) {
	byX[stars[i].first.second].push_back(i);
    }


    set<pair<int,int>> st; //(a[i],i)
    stack<int> stk;
    st.insert({0,0});
    stk.push(0); // monoincreasing

    for (int i=1; i<=n; i++) {
	while (!stk.empty() && a[i]<=a[stk.top()]) {
	    st.erase({a[stk.top()],stk.top()});
	    stk.pop();
	}
	for (int idx: byX[i]) {
	    int y = stars[idx].first.first;
	    pre[idx] = prev(st.upper_bound({y,-1}))->second+1;
	}

	stk.push(i);
	st.insert({a[i],i});
    }

    while (stk.size()) stk.pop();
    st.clear();

    st.insert({0,n+1});
    stk.push(n+1);

    for (int i=n; i>=1; i--) {
	while (!stk.empty() && a[i]<=a[stk.top()]) {
	    st.erase({a[stk.top()],stk.top()});
	    stk.pop();
	}
	for (int idx: byX[i]) {
	    int y = stars[idx].first.first;
	    nex[idx] = prev(st.upper_bound({y,-1}))->second-1;
	}

	stk.push(i);
	st.insert({a[i],i});
    }


    // for (int i=0; i<m; i++) {
    // 	cout<<i+1<<": "<<pre[i]<<" "<<nex[i]<<endl;
    // }


    segtree tree;
    tree.init(n+10);

    for (int i=0; i<m; i++) {
	auto star = stars[i];
	int x = star.first.second;
	ll c = star.second;

	ll val = c + tree.qry(1,1,n,x,x);
	if (val>0) {
	    sum -= val;
	    tree.upd(1,1,n,pre[i],nex[i],-val);
	}
	
    }


    cout<<sum<<endl;    
    return 0;
}

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