Submission #205999

#	Time	Username	Problem	Language	Result	Execution time	Memory
205999		arnold518	Fire (JOI20_ho_t5)	C++14	100 / 100	378 ms	41544 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

struct Query { ll x, y, idx; };
struct Point { ll x, y, v; };

struct Line
{
	ll a, b;
	Line() : a(0), b(0) {}
	Line(ll a, ll b) : a(a), b(b) {}
};
Line operator + (const Line &p, const Line &q) { return Line(p.a+q.a, p.b+q.b); }

int N, Q;
ll A[MAXN+10], B[MAXN+10];
vector<Query> query;
vector<Point> point;

struct BIT
{
	Line tree[MAXN+10];
	BIT() { for(int i=0; i<MAXN+10; i++) tree[i]=Line(); }
	void update(int i, Line p) { for(; i<=N+1; i+=(i&-i)) tree[i]=tree[i]+p; }
	Line query(int i) { Line ret; for(; i>0; i-=(i&-i)) ret=ret+tree[i]; return ret; }
} bit;

ll ans[MAXN+10];

int main()
{
	int i, j, k;

	scanf("%d%d", &N, &Q);
	for(i=1; i<=N; i++) scanf("%lld", &A[i]), B[i]=B[i-1]+A[i];
	for(i=1; i<=Q; i++)
	{
		ll t, l, r;
		scanf("%lld%lld%lld", &t, &l, &r);
		query.push_back({l-1, t, -i});
		query.push_back({r, t, i});
		ans[i]+=B[r]-B[l-1];
	}

	vector<int> S;
	for(i=1; i<=N; i++)
	{
		while(!S.empty() && A[S.back()]<=A[i])
		{
			if(S.size()>=2)
			{
				int p=S[S.size()-2], q=S[S.size()-1];
				point.push_back({q, q-p, A[p]-A[q]});
				point.push_back({i, i-p, -A[p]+A[q]});
			}
			S.pop_back();
		}
		S.push_back(i);
	}
	while(!S.empty())
	{
		if(S.size()>=2)
		{
			int p=S[S.size()-2], q=S[S.size()-1];
			point.push_back({q, q-p, A[p]-A[q]});
			point.push_back({i, i-p, -A[p]+A[q]});
		}
		S.pop_back();
	}

	bit=BIT();
	sort(point.begin(), point.end(), [&](const Point &p, const Point &q) { return p.y-p.x<q.y-q.x; });
	sort(query.begin(), query.end(), [&](const Query &p, const Query &q) { return p.y-p.x<q.y-q.x; });

	for(i=0, j=0; i<query.size(); i++)
	{
		for(; j<point.size() && point[j].y-point[j].x<=query[i].y-query[i].x; j++) bit.update(point[j].x, {point[j].v, -point[j].v*(point[j].x-1)});
		Line t=bit.query(query[i].x);
		if(query[i].idx>0) ans[query[i].idx]+=t.a*query[i].x+t.b;
		else ans[-query[i].idx]-=t.a*query[i].x+t.b;
	}

	bit=BIT();
	sort(point.begin(), point.end(), [&](const Point &p, const Point &q) { return p.y-p.x>q.y-q.x; });
	sort(query.begin(), query.end(), [&](const Query &p, const Query &q) { return p.y-p.x>q.y-q.x; });

	for(i=0, j=0; i<query.size(); i++)
	{
		for(; j<point.size() && point[j].y-point[j].x>query[i].y-query[i].x; j++) bit.update(point[j].y, {point[j].v, -point[j].v*(point[j].y-1)});
		Line t=bit.query(query[i].y);
		if(query[i].idx>0) ans[query[i].idx]+=t.a*query[i].y+t.b;
		else ans[-query[i].idx]-=t.a*query[i].y+t.b;
	}

	for(i=1; i<=Q; i++) printf("%lld\n", ans[i]);
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0, j=0; i<query.size(); i++)
                ~^~~~~~~~~~~~~
ho_t5.cpp:83:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<point.size() && point[j].y-point[j].x<=query[i].y-query[i].x; j++) bit.update(point[j].x, {point[j].v, -point[j].v*(point[j].x-1)});
         ~^~~~~~~~~~~~~
ho_t5.cpp:93:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0, j=0; i<query.size(); i++)
                ~^~~~~~~~~~~~~
ho_t5.cpp:95:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<point.size() && point[j].y-point[j].x>query[i].y-query[i].x; j++) bit.update(point[j].y, {point[j].v, -point[j].v*(point[j].y-1)});
         ~^~~~~~~~~~~~~
ho_t5.cpp:38:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
ho_t5.cpp:40: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:41:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld", &A[i]), B[i]=B[i-1]+A[i];
                      ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
ho_t5.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &t, &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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