Submission #545062

#	Time	Username	Problem	Language	Result	Execution time	Memory
545062		Asymmetry	Fire (JOI20_ho_t5)	C++17	100 / 100	406 ms	47216 KiB

ho_t5

//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

struct pytanie {
	int l, r, id;
};

struct SegTree {
	struct node {
		long long A, B;
	};
	vector<node> st;
	int com;
	
	SegTree(int n) {
		com = 1;
		while (com < n) {
			com <<= 1;
		}
		st.resize(com << 1);
		--com;
	}
	
	void wstaw(int x, long long A, long long B) {
		x += com;
		st[x] = {A, B};
		x >>= 1;
		while (x) {
			st[x] = {st[x * 2].A + st[x * 2 + 1].A, st[x * 2].B + st[x * 2 + 1].B};
			x >>= 1;
		}
	}
	
	long long pytaj(int a, int b, int tm) {
		a += com;
		b += com + 1;
		long long ret = 0;
		while (a < b) {
			if (a & 1) {
				ret += st[a].A * tm + st[a].B;
				++a;
			}
			if (b & 1) {
				ret += st[b - 1].A * tm + st[b - 1].B;
			}
			a >>= 1;
			b >>= 1;
		}
		return ret;
	}
};

struct nod {
	int lf, rg;
};

//~ const int N = 100;
const int N = 201000;
int n, q, com;
int t[N];
int lf[N]; // następny na lewo większy
int rg[N]; // następny na prawo większy równy
int slp[N]; // aktualny slope
long long odp[N];
vector<pytanie> pyt[N]; // zapytania po czasie
vector<int> zgon[N]; // kto właśnie znika
vector<int> slope[N]; // komu maleje slope w tym momencie
vector<nod> ts;

int kiedy_zgon(int x) { // pierwszy moment nieistnienia x
	if (lf[x] == 0) {
		return 1e9;
	}
	return rg[x] - lf[x] - 1;
}

pair<int, int> aktualny(int x, int tm) { // aktualny przedział pożaru x w momencie tm
	int l = x;
	if (lf[x]) {
		l = max(l, lf[x] + tm + 1);
	}
	int r = min(rg[x] - 1, x + tm);
	return {l, r};
}

void update(int x) {
	int l = x << 1;
	int r = l ^ 1;
	ts[x] = {min(ts[l].lf, ts[r].lf), max(ts[l].rg, ts[r].rg)};
}

// pożar, który posiada w sobie p w momencie tm
int fin(int x, int l, int r, int tm, int p) {
	if (l == r) {
		return l;
	}
	if (ts[x * 2].lf > ts[x * 2].rg) {
		return fin(x * 2 + 1, (l + r) / 2 + 1, r, tm, p);
	}
	auto lf = aktualny(ts[x * 2].rg, tm);
	if (lf.second < p) {
		return fin(x * 2 + 1, (l + r) / 2 + 1, r, tm, p);
	}
	return fin(x * 2, l, (l + r) / 2, tm, p);
}

void zgas(int x) {
	x += com;
	ts[x] = {(int)1e9, (int)-1e9};
	x >>= 1;
	while (x) {
		update(x);
		x >>= 1;
	}
}

int main() {
	scanf("%d%d", &n, &q);
	com = 1;
	while (com < n) {
		com <<= 1;
	}
	ts.resize(com << 1);
	--com;
	SegTree st(n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &t[i]);
		st.wstaw(i, t[i], t[i]);
		ts[i + com] = {i, i};
		slp[i] = 1;
	}
	for (int i = n + 1; i <= com + 1; ++i) {
		ts[i + com] = {(int)1e9, (int)-1e9};
	}
	
	for (int i = com; i; --i) {
		update(i);
	}
	
	t[0] = 1e9 + 7;
	t[n + 1] = 1e9 + 7;
	for (int i = 1; i <= n; ++i) {
		lf[i] = i - 1;
		while (t[i] >= t[lf[i]]) {
			lf[i] = lf[lf[i]];
		}
	}
	
	for (int i = n; i; --i) {
		rg[i] = i + 1;
		while (t[i] > t[rg[i]]) {
			rg[i] = rg[rg[i]];
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		int x = kiedy_zgon(i);
		//~ debug(i, x);
		if (x <= n) {
			zgon[x].push_back(i);
		}
		
		if (lf[i]) {
			slope[i - lf[i] - 1].push_back(i);
		}
		
		slope[rg[i] - i - 1].push_back(i);
	}
	
	//~ for (int i = 0; i <= n; ++i) {
		//~ debug(i, slope[i]);
	//~ }
	
	//~ for (int i = 0; i <= n; ++i) {
		//~ for (int j = 1; j <= n; ++j) {
			//~ debug(i, j, aktualny(j, i));
		//~ }
	//~ }
	
	for (int i = 1; i <= q; ++i) {
		int a, b, c;
		scanf("%d%d%d", &c, &a, &b);
		pyt[c].push_back({a, b, i});
	}
	
	for (int tm = 0; tm <= n; ++tm) {
		//~ debug(tm);
		for (int i : zgon[tm]) {
			//~ debug("ZGON", i);
			zgas(i);
			st.wstaw(i, 0, 0);
		}
		
		for (int i : slope[tm]) {
			if (slp[i] == 1) { // zamiana na stały
				auto x = aktualny(i, tm);
				//~ debug(i, x);
				st.wstaw(i, 0, (long long)(x.second - x.first + 1) * t[i]);
			}
			else { // zamiana na malejący
				auto x = aktualny(i, tm);
				//~ debug(i, x);
				st.wstaw(i, -t[i], (long long)(tm + x.second - x.first + 1) * t[i]);
			}
			--slp[i];
			//~ debug(i, slp[i]);
		}
		
		//~ for (int i = 1; i <= n; ++i) {
			//~ printf("%lld ", st.pytaj(i, i, tm));
		//~ }
		//~ printf("\n");
		
		for (auto i : pyt[tm]) {
			int poc = fin(1, 1, com + 1, tm, i.l);
			int kon = fin(1, 1, com + 1, tm, i.r);
			auto p = aktualny(poc, tm);
			auto k = aktualny(kon, tm);
			//~ debug(i.l, i.r, i.id, poc, kon, p, k);
			odp[i.id] = st.pytaj(poc, kon, tm) - (long long)(i.l - p.first) * t[poc] - (long long)(k.second - i.r) * t[kon];
		}
	}
	
	for (int i = 1; i <= q; ++i) {
		printf("%lld\n", odp[i]);
	}
	return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   scanf("%d", &t[i]);
      |   ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:190:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |   scanf("%d%d%d", &c, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80