oj.uz

답안 #545059

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545059 2022-04-03T13:20:57 Z Asymmetry Fire (JOI20_ho_t5) C++17
6 / 100
 437 ms 46624 KB 
//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 = 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, (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

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

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 12 ms 14468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 240 ms 45776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 291 ms 46624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 412 ms 42500 KB Output is correct
2 Correct 423 ms 42460 KB Output is correct
3 Correct 399 ms 42872 KB Output is correct
4 Correct 415 ms 42772 KB Output is correct
5 Correct 379 ms 42736 KB Output is correct
6 Correct 408 ms 42496 KB Output is correct
7 Correct 378 ms 42724 KB Output is correct
8 Correct 417 ms 42716 KB Output is correct
9 Correct 371 ms 42816 KB Output is correct
10 Correct 395 ms 42656 KB Output is correct
11 Correct 402 ms 42852 KB Output is correct
12 Correct 437 ms 42796 KB Output is correct
13 Correct 366 ms 42740 KB Output is correct
14 Correct 409 ms 42764 KB Output is correct

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 12 ms 14468 KB Output isn't correct
3 Halted 0 ms 0 KB -