Submission #285800

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
285800	2020-08-29T15:39:33 Z	limabeans	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	142 ms	14840 KB

election_campaign

#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 ll mod = 1e9+7;
const int maxn = 1e5 + 5;
const ll inf = 1e18;

struct MaxLazySegmentTree {
    vector<ll> t, o;
    void init(int n) {
	n += 10;
	t.resize(4*n);
	o.resize(4*n);
    }
    
    void push(int v) {
	t[2*v]+=o[v];
	t[2*v+1]+=o[v];
	o[2*v]+=o[v];
	o[2*v+1]+=o[v];
	o[v]=0;
    }

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

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


int n, x[maxn], y[maxn];
int m;
int a[maxn], b[maxn], c[maxn];

vector<int> ev[maxn];

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

    cin>>n;
    for (int i=0; i<n-1; i++) {
	cin>>x[i]>>y[i];
	assert(x[i]==i+1);
	assert(y[i]==x[i]+1);
    }

    cin>>m;
    for (int i=0; i<m; i++) {
	cin>>a[i]>>b[i]>>c[i];
	if (a[i]>b[i]) swap(a[i],b[i]);
	ev[b[i]].push_back(i);
    }

    MaxLazySegmentTree dp;
    dp.init(n+10);

    auto qry = [&](int i) {
	if (i==0) return 0ll;
	return dp.queryMax(1,1,n,1,i);
    };

    auto upd = [&](int i, ll val) {
	ll cur = dp.queryMax(1,1,n,i,i);
	if (val <= cur) return;
	ll dx = val-cur;
	dp.rangeAdd(1,1,n,i,i,dx);
    };


    for (int i=1; i<=n; i++) {
	for (int idx: ev[i]) {
	    int l = a[idx];
	    int r = b[idx];
	    int val = c[idx];
	    upd(r, val+qry(l-1));
	}
    }

    ll res = qry(n);
    cout<<res<<endl;    
    return 0;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Runtime error	6 ms	5248 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	3 ms	2816 KB	Output is correct
4	Correct	126 ms	12316 KB	Output is correct
5	Correct	118 ms	12280 KB	Output is correct
6	Correct	114 ms	12284 KB	Output is correct
7	Correct	126 ms	12280 KB	Output is correct
8	Correct	116 ms	12280 KB	Output is correct
9	Correct	113 ms	12280 KB	Output is correct
10	Correct	118 ms	12280 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	3 ms	2816 KB	Output is correct
4	Correct	126 ms	12316 KB	Output is correct
5	Correct	118 ms	12280 KB	Output is correct
6	Correct	114 ms	12284 KB	Output is correct
7	Correct	126 ms	12280 KB	Output is correct
8	Correct	116 ms	12280 KB	Output is correct
9	Correct	113 ms	12280 KB	Output is correct
10	Correct	118 ms	12280 KB	Output is correct
11	Correct	14 ms	3456 KB	Output is correct
12	Correct	128 ms	14752 KB	Output is correct
13	Correct	120 ms	14840 KB	Output is correct
14	Correct	122 ms	14840 KB	Output is correct
15	Correct	119 ms	14712 KB	Output is correct
16	Correct	125 ms	14840 KB	Output is correct
17	Correct	127 ms	14712 KB	Output is correct
18	Correct	121 ms	14712 KB	Output is correct
19	Correct	125 ms	14840 KB	Output is correct
20	Correct	142 ms	14840 KB	Output is correct