Submission #287285

#	Time	Username	Problem	Language	Result	Execution time	Memory
287285		arnold518	Fire (JOI20_ho_t5)	C++14	100 / 100	417 ms	30272 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;

int N, Q, A[MAXN+10];
ll B[MAXN+10];

struct Data
{
	int y, x, p;
};

vector<Data> AV, QV;
ll ans[MAXN+10];

pll tree[MAXN+10];
pll operator + (const pll &p, const pll &q) { return {p.first+q.first, p.second+q.second}; }
void update(int i, pll p) { for(; i<=N; i+=(i&-i)) tree[i]=tree[i]+p; }
pll query(int i) { pll ret={0, 0}; for(; i>0; i-=(i&-i)) ret=ret+tree[i]; return ret; }

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

	vector<int> S;
	for(int i=1; i<=N+1; i++)
	{
		int bef;
		if(!S.empty()) bef=A[S.back()];
		while(!S.empty() && A[S.back()]<=A[i])
		{
			int y1=1, x1=S.back()+1, p=A[S.back()]-bef;
			int y2=i-S.back(), x2=i;
			AV.push_back({y1, x1, p});
			AV.push_back({y2, x2, -p});

			bef=A[S.back()];
			S.pop_back();
		}
		if(!S.empty())
		{
			int y1=1, x1=S.back()+1, p=A[i]-bef;
			int y2=i-S.back(), x2=i;
			AV.push_back({y1, x1, p});
			AV.push_back({y2, x2, -p});
		}
		S.push_back(i);
	}

	sort(AV.begin(), AV.end(), [&](const Data &p, const Data &q) { return p.y-p.x<q.y-q.x; });
	sort(QV.begin(), QV.end(), [&](const Data &p, const Data &q) { return p.y-p.x<q.y-q.x; });

	for(int i=0; i<=N; i++) tree[i]={0, 0};

	for(int i=0, j=0; i<QV.size(); i++)
	{
		for(; j<AV.size() && AV[j].y-AV[j].x<=QV[i].y-QV[i].x; j++)
		{
			update(AV[j].x, pll(AV[j].p, (ll)AV[j].p*(1-AV[j].x)));
		}
		pll ret=query(QV[i].x);
		if(QV[i].p>0) ans[QV[i].p]+=ret.first*QV[i].x+ret.second;
		else ans[-QV[i].p]-=ret.first*QV[i].x+ret.second;
	}

	reverse(AV.begin(), AV.end());
	reverse(QV.begin(), QV.end());

	for(int i=0; i<=N; i++) tree[i]={0, 0};

	for(int i=0, j=0; i<QV.size(); i++)
	{
		for(; j<AV.size() && AV[j].y-AV[j].x>=QV[i].y-QV[i].x+1; j++)
		{
			update(AV[j].y, pll(AV[j].p, (ll)AV[j].p*(1-AV[j].y)));	
		}
		pll ret=query(QV[i].y);
		if(QV[i].p>0) ans[QV[i].p]+=ret.first*QV[i].y+ret.second;
		else ans[-QV[i].p]-=ret.first*QV[i].y+ret.second;
	}
	for(int i=1; i<=Q; i++) printf("%lld\n", ans[i]);
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i=0, j=0; i<QV.size(); i++)
      |                    ~^~~~~~~~~~
ho_t5.cpp:73:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(; j<AV.size() && AV[j].y-AV[j].x<=QV[i].y-QV[i].x; j++)
      |         ~^~~~~~~~~~
ho_t5.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i=0, j=0; i<QV.size(); i++)
      |                    ~^~~~~~~~~~
ho_t5.cpp:89:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for(; j<AV.size() && AV[j].y-AV[j].x>=QV[i].y-QV[i].x+1; j++)
      |         ~^~~~~~~~~~
ho_t5.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:29:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   scanf("%d%d%d", &t, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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