Submission #201229

#	Time	Username	Problem	Language	Result	Execution time	Memory
201229		ainta	Fire (JOI20_ho_t5)	C++17	100 / 100	499 ms	28920 KiB

ho_t5

#include<cstdio>
#include<algorithm>
#define N_ 201000
#define SZ 262144
using namespace std;
int n, Q, st[N_], w[N_], cnt;
int Right[N_], Left[N_];
struct point {
	int ck, x, y, c;
	bool operator < (const point &p)const {
		return x - y < p.x - p.y;
	}
}U[N_*10];
long long Res[N_];
void Add(int x, int y, int c) {
	U[cnt++] = { 0,x,y,c };
}
struct AA {
	long long BIT[N_];
	void init() {
		for (int i = 0; i < N_; i++)BIT[i] = 0;
	}
	void Add(int a, long long b) {
		while (a < N_) {
			BIT[a] += b;
			a += (a&-a);
		}
	}
	long long Sum(int a) {
		long long r = 0;
		while (a) {
			r += BIT[a];
			a -= (a&-a);
		}
		return r;
	}
}B1, B2;
void Add2(int x, long long c) {
	B1.Add(x, c);
	B2.Add(x, c*(-x + 1));
}
long long Calc(int x) {
	return B1.Sum(x) * x + B2.Sum(x);
}
int main() {
	int i;
	scanf("%d%d", &n, &Q);
	int top = 0;
	for (i = 1; i <= n+1; i++) {
		if(i!=n+1)scanf("%d", &w[i]);
		while (top && (i==n+1 || w[st[top]] < w[i])) {
			Right[st[top]] = i;
			top--;
		}
		Left[i] = st[top];
		st[++top] = i;
	}
	for (i = 1; i <= n; i++) {
		Add(1, i, w[i]);
		if (Left[i] != 0) {
			Add(i - Left[i] + 1, i, -w[i]);
		}
		if (Right[i] != n+1) {
			Add(Right[i] - i + 1, Right[i], -w[i]);
		}
		if (Left[i] != 0 && Right[i] != n+1) {
			Add(Right[i] - Left[i] + 1, Right[i], w[i]);
		}
	}
	for (i = 1; i <= Q; i++) {
		int t, b, e;
		scanf("%d%d%d", &t, &b, &e);
		t++;
		U[cnt++] = { 1,t,e,i };
		U[cnt++] = { 1,t,b-1,-i };
	}
	sort(U, U + cnt);
	for (i = 0; i < cnt; i++) {
		if (U[i].ck == 0) {
			Add2(U[i].y, U[i].c);
		}
		else {
			long long t = Calc(U[i].y);
			if (U[i].c < 0)Res[-U[i].c] -= t;
			else Res[U[i].c] += t;
		}
	}
	B1.init();
	B2.init();
	for (i = cnt - 1; i >= 0; i--) {
		if (U[i].ck == 0) {
			Add2(U[i].x, U[i].c);
		}
		else {
			long long t = Calc(U[i].x);
			if (U[i].c < 0)Res[-U[i].c] -= t;
			else Res[U[i].c] += t;
		}
	}
	for (i = 1; i <= Q; i++)printf("%lld\n", Res[i]);
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:50:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(i!=n+1)scanf("%d", &w[i]);
             ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t, &b, &e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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