Submission #285484

#	Time	Username	Problem	Language	Result	Execution time	Memory
285484		arnold518	Progression (NOI20_progression)	C++14	100 / 100	1954 ms	95504 KiB

Progression

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

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

const int MAXN = 3e5;

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

struct Node
{
	ll sum, len, cnt, lval, lcnt, rval, rcnt;
	Node() : sum(0), len(0), cnt(0), lval(-1), lcnt(0), rval(-1), rcnt(0) {}
};

Node operator + (const Node &p, const Node &q)
{
	Node ret;
	ret.sum=p.sum+q.sum;
	ret.len=p.len+q.len;
	ret.lval=p.lval;
	ret.lcnt=p.lcnt;
	if(p.lcnt==p.len && q.lval==p.lval) ret.lcnt=p.lcnt+q.lcnt;
	ret.rval=q.rval;
	ret.rcnt=q.rcnt;
	if(q.rcnt==q.len && p.rval==q.rval) ret.rcnt=p.rcnt+q.rcnt;
	ret.cnt=max(p.cnt, q.cnt);
	if(p.rval==q.lval) ret.cnt=max(ret.cnt, p.rcnt+q.lcnt);
	return ret;	
}

Node tree[MAXN*4+10];
pll lazy[MAXN*4+10];

void busy(int node, int tl, int tr)
{
	if(lazy[node].first==0) return;
	else if(lazy[node].first==1)
	{
		tree[node].sum+=lazy[node].second*tree[node].len;
		tree[node].lval+=lazy[node].second;
		tree[node].rval+=lazy[node].second;

		if(tl!=tr)
		{
			if(lazy[node*2].first==0) lazy[node*2]=lazy[node];
			else lazy[node*2].second+=lazy[node].second;

			if(lazy[node*2+1].first==0) lazy[node*2+1]=lazy[node];
			else lazy[node*2+1].second+=lazy[node].second;			
		}
	}
	else if(lazy[node].first==2)
	{
		tree[node].sum=lazy[node].second*tree[node].len;
		tree[node].cnt=tree[node].lcnt=tree[node].rcnt=tree[node].len;
		tree[node].lval=tree[node].rval=lazy[node].second;

		if(tl!=tr)
		{
			lazy[node*2]=lazy[node];
			lazy[node*2+1]=lazy[node];
		}
	}
	lazy[node]=pll(0, 0);
}

void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		tree[node].sum=A[tl];
		tree[node].len=1;
		tree[node].cnt=tree[node].lcnt=tree[node].rcnt=1;
		tree[node].lval=tree[node].rval=A[tl];
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	tree[node]=tree[node*2]+tree[node*2+1];
}

void update1(int node, int tl, int tr, int l, int r, ll k)
{
	l=max(1, l); r=min(N, r);
	if(l>r) return;
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		lazy[node]=pll(1, k);
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update1(node*2, tl, mid, l, r, k);
	update1(node*2+1, mid+1, tr, l, r, k);
	tree[node]=tree[node*2]+tree[node*2+1];
}

void update2(int node, int tl, int tr, int l, int r, ll k)
{
	l=max(1, l); r=min(N, r);
	if(r>N) return;
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		lazy[node]=pll(2, k);
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update2(node*2, tl, mid, l, r, k);
	update2(node*2+1, mid+1, tr, l, r, k);
	tree[node]=tree[node*2]+tree[node*2+1];
}

Node query(int node, int tl, int tr, int l, int r)
{
	l=max(1, l); r=min(N, r);
	if(l>r) return Node();
	busy(node, tl, tr);
	if(l==tl && tr==r) return tree[node];
	int mid=tl+tr>>1;
	if(r<=mid) return query(node*2, tl, mid, l, r);
	if(mid+1<=l) return query(node*2+1, mid+1, tr, l, r);
	return query(node*2, tl, mid, l, mid)+query(node*2+1, mid+1, tr, mid+1, r);
}

void debug(int node, int tl, int tr)
{
	busy(node, tl, tr);
	if(tl==tr) return;
	int mid=tl+tr>>1;
	debug(node*2, tl, mid);
	debug(node*2+1, mid+1, tr);
	tree[node]=tree[node*2]+tree[node*2+1];
	Node &t=tree[node];
	printf("DEBUG %d %d : sum %lld len %lld cnt %lld lval %lld lcnt %lld rval %lld rcnt %lld\n", tl, tr, t.sum, t.len, t.cnt, t.lval, t.lcnt, t.rval, t.rcnt);
}

int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++) scanf("%lld", &A[i]);

	for(int i=N; i>=1; i--) A[i]=A[i]-A[i-1];
	init(1, 1, N);

	while(Q--)
	{
		//for(int i=1; i<=N; i++) printf("%lld ", query(1, 1, N, 1, i).sum); printf("\n");
		//debug(1, 1, N);
		int t, l, r, s, c;
		scanf("%d", &t);
		if(t==1)
		{
			scanf("%d%d%d%d", &l, &r, &s, &c);
			int t=query(1, 1, N, 1, r+1).sum;
			update1(1, 1, N, l+1, r, c);
			update1(1, 1, N, l, l, s);
			t-=query(1, 1, N, 1, r).sum;
			update2(1, 1, N, r+1, r+1, t);
		}
		else if(t==2)
		{
			scanf("%d%d%d%d", &l, &r, &s, &c);
			int t=query(1, 1, N, 1, r+1).sum;
			update2(1, 1, N, l+1, r, c);
			update2(1, 1, N, l, l, -query(1, 1, N, 1, l-1).sum+s);
			t-=query(1, 1, N, 1, r).sum;
			update2(1, 1, N, r+1, r+1, t);
		}
		else if(t==3)
		{
			int l, r;
			scanf("%d%d", &l, &r);
			if(l==r) printf("1\n");
			else printf("%d\n", query(1, 1, N, l+1, r).cnt+1);
			Node t=query(1, 1, N, l+1, r);
			//printf("Query %lld %lld %lld %lld %lld %lld %lld\n", t.sum, t.len, t.cnt, t.lval, t.lcnt, t.rval, t.rcnt);
		}
	}
}

Compilation message (stderr)

Progression.cpp: In function 'void init(int, int, int)':
Progression.cpp:81:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |  int mid=tl+tr>>1;
      |          ~~^~~
Progression.cpp: In function 'void update1(int, int, int, int, int, ll)':
Progression.cpp:99:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |  int mid=tl+tr>>1;
      |          ~~^~~
Progression.cpp: In function 'void update2(int, int, int, int, int, ll)':
Progression.cpp:117:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |  int mid=tl+tr>>1;
      |          ~~^~~
Progression.cpp: In function 'Node query(int, int, int, int, int)':
Progression.cpp:129:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  129 |  int mid=tl+tr>>1;
      |          ~~^~~
Progression.cpp: In function 'void debug(int, int, int)':
Progression.cpp:139:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |  int mid=tl+tr>>1;
      |          ~~^~~
Progression.cpp: In function 'int main()':
Progression.cpp:184:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
  184 |    else printf("%d\n", query(1, 1, N, l+1, r).cnt+1);
      |                 ~^     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                  |                               |
      |                  int                             ll {aka long long int}
      |                 %lld
Progression.cpp:185:9: warning: variable 't' set but not used [-Wunused-but-set-variable]
  185 |    Node t=query(1, 1, N, l+1, r);
      |         ^
Progression.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Progression.cpp:150:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
Progression.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
Progression.cpp:163:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |    scanf("%d%d%d%d", &l, &r, &s, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:172:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  172 |    scanf("%d%d%d%d", &l, &r, &s, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:182:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  182 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17