Submission #218949

#	Time	Username	Problem	Language	Result	Execution time	Memory
218949		mieszko11b	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	13 ms	14720 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;
using ll = long long;

#define X first
#define Y second

const int inf = int(1e9)+ 7;

struct Star {
	int x, y, c;
	
	Star(int x, int y, int c) {
		this->x = x;
		this->y = y;
		this->c = c;
	}
};

struct SegmentTree {
	int lv;
	vector<ll> d;
	
	SegmentTree(int n) {
		lv = 2;
		while(lv < n + 3)
			lv *= 2;
		d.resize(2 * lv + 2);
	}
	
	void insert(int a, int b, ll v) {
		if(b < a)
			return ;
			
		int va = a + lv;
		int vb = b + lv;
		d[va] += v;
		if(va != vb)
			d[vb] += v;
		while(va / 2 != vb / 2) {
			if(va % 2 == 0)
				d[va + 1] += v;
			if(vb % 2 == 1)
				d[vb - 1] += v;
			va /= 2;
			vb /= 2;
		}
	}
	
	ll query(int x) {
		int w = x + lv;
		ll res = 0;
		while(w) {
			res += d[w];
			w /= 2;
		}
		return res;
	}
};

int n, m;
int a[200007];
int pl[200007], pr[200007];
int maxr[200007], maxl[200007];
vector<Star> St[200007];

struct Tree {
	int jp[20][200007];
	vector<int> ch[200007];
	int ord[200007], max_ord[200007];
	SegmentTree *ST;
	int nxt_num;
	
	void dfs(int w) {
		ord[w] = nxt_num++;
		for(int u : ch[w])
			dfs(u);
		max_ord[w] = nxt_num - 1;
	}
	
	Tree(int *p) {
		for(int i = 1 ; i <= n ; i++) {
			jp[0][i] = p[i];
			ch[p[i]].push_back(i);
		}
		for(int j = 1 ; j <= 18 ; j++)
			for(int i = 1 ; i <= n ; i++)
				jp[j][i] = jp[j - 1][jp[j - 1][i]];
		ST = new SegmentTree(n);
		
		nxt_num = 0;
		dfs(0);
	}
	
	int first_atleast(int i, int h) {
		for(int j = 18 ; j >= 0 ; j--)
			if(a[jp[j][i]] < h)
				i = jp[j][i];
		i = jp[0][i];
		return i;
	}
	
	void insert(int i, ll v) {
		ST->insert(ord[i], max_ord[i], v);
	}
	
	ll query(int a, int b) {
		if(ord[a] > ord[b])
			swap(a, b);
		//a przodkiem b
		return ST->query(ord[b]) - ST->query(a);
	}
};

Tree *LT, *RT;
ll sum_all;

int main() {
	scanf("%d", &n);
	for(int i = 1 ; i <= n ; i++)
		scanf("%d", &a[i]);
	a[0] = a[n + 1] = inf;
	
	stack<int> S;
	S.push(0);
	for(int i = 1 ; i <= n ; i++) {
		while(a[S.top()] <= a[i])
			S.pop();
		pl[i] = S.top();
		maxr[S.top()] = i;
		S.push(i);
	}
	while(!S.empty())
		S.pop();
	S.push(0);
	for(int i = n ; i >= 1 ; i--) {
		while(a[S.top()] <= a[i])
			S.pop();
		pr[i] = S.top();
		maxl[S.top()] = i;
		S.push(i);
	}
	
	LT = new Tree(pl);
	RT = new Tree(pr);
	
	scanf("%d", &m);
	while(m--) {
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		sum_all += c;
		int l = LT->first_atleast(x, y);
		int r = RT->first_atleast(x, y);
		
		if(a[l] <= a[r])
			St[l].emplace_back(x, y, c);
		if(a[r] <= a[l])
			St[r].emplace_back(x, y, c);
		//~ cout << l << endl;
	}
	
	vector<ii> V(n);
	for(int i = 0 ; i < n ; i++)
		V[i] = {a[i + 1], i + 1};
	
	sort(V.begin(), V.end());
	
	for(auto p : V) {
		int i = p.Y;
		ll dpl = LT->query(maxl[i], pl[i]) + RT->query(maxl[i], i);
		ll dpr = LT->query(maxr[i], i) + RT->query(maxr[i], pr[i]);
		for(auto s : St[i]) {
			if(s.x > i)
				dpr = max(dpr, (ll)s.c + LT->query(s.x, i) + RT->query(s.x, pr[i]));
			else
				dpl = max(dpl, (ll)s.c + LT->query(s.x, pl[i]) + RT->query(s.x, i));
		}
		
		LT->insert(i, dpl);
		RT->insert(i, dpr);
		
		//~ cout << i << " " << dpl << " " << dpr << endl;
	}
	//~ cout << maxr[0] << endl;
	ll res = LT->query(maxr[0], 0) + RT->query(maxr[0], 0);
	for(auto s : St[0]) {
		res = max(res, (ll)s.c + LT->query(s.x, 0) + RT->query(s.x, 0));
	}
	printf("%lld\n", sum_all - res);
	
	return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
constellation3.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
constellation3.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
constellation3.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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