Submission #73826

#	Time	Username	Problem	Language	Result	Execution time	Memory
73826		ainta	Gorgeous Pill (FXCUP3_gorgeous)	C++14	100 / 100	407 ms	32284 KiB

gorgeous

#include<cstdio>
#include<algorithm>
#include<vector>
#define pil pair<int,long long>
#define N_ 301000
#define SZ 524288
using namespace std;
struct point {
	int b, e, c, ck;
	bool operator <(const point &p)const {
		return b != p.b ? b<p.b : e>p.e;
	}
}P[N_*3];
int w[N_], cnt, C[N_];
int n;
long long IT[SZ + SZ], D[N_*3], Res[N_];
void Put(int a, long long b) {
	a += SZ;
	while (a) {
		IT[a] = max(IT[a], b);
		a >>= 1;
	}
}
long long Max(int b, int e) {
	long long r = 0;
	b += SZ, e += SZ;
	while (b <= e) {
		r = max(r, max(IT[b], IT[e]));
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	return r;
}
void Calc(int a) {
	int b = P[a].b, e = P[a].e;
	D[a] = Max(e, n) + P[a].c;
}
int main() {
	int i;
	scanf("%d", &n);
	P[cnt++] = { 1,n,0 };
	for (i = 1; i <= n; i++) scanf("%d", &w[i]);
	for (i = 1; i <= n; i++){
		scanf("%d", &C[i]);
		if (i - w[i] + 1 >= 1)P[cnt++] = { i - w[i] + 1, i, C[i], 1 };
		if (i + w[i] - 1 <= n)P[cnt++] = { i, i + w[i] - 1, C[i], 0 };
		if(w[i] != 1)P[cnt++] = { i,i,0,0 };
	}
	sort(P, P + cnt);
	vector<pil>V;
	for (i = 0; i < cnt; i++) {
		if (i && P[i].b != P[i - 1].b) {
			for (auto &x : V) Put(x.first, x.second);
			V.clear();
		}
		Calc(i);
		if (P[i].ck == 1)Put(P[i].e - 1, D[i]);
		else V.push_back({ P[i].e, D[i] });
	}
	for (i = 0; i < cnt; i++) {
		if (P[i].b == P[i].e)Res[P[i].b] = max(Res[P[i].b], D[i]);
	}
	for (i = 1; i <= n; i++)printf("%lld ", Res[i]);
}

Compilation message (stderr)

gorgeous.cpp: In function 'void Calc(int)':
gorgeous.cpp:34:6: warning: unused variable 'b' [-Wunused-variable]
  int b = P[a].b, e = P[a].e;
      ^
gorgeous.cpp: In function 'int main()':
gorgeous.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
gorgeous.cpp:41:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++) scanf("%d", &w[i]);
                           ~~~~~^~~~~~~~~~~~~
gorgeous.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &C[i]);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 39 / 39
• Subtask 3: 49 / 49