Submission #61592915

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define int long long
//#define USE_FREOPEN
//#define MUL_TEST
#define FILENAME ""
using namespace std;
struct Seg
{
  int l,r,sum,laz;
  #define l(p) tr[p].l
  #define r(p) tr[p].r
  #define sum(p) tr[p].sum
  #define laz(p) tr[p].laz
}tr[2500005];
int a[500005];
void pushup(int p)
{
  sum(p) = sum(p << 1) + sum(p << 1 | 1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
#define int long long
//#define USE_FREOPEN
//#define MUL_TEST
#define FILENAME ""
using namespace std;

struct Seg
{
	int l,r,sum,laz;
	#define l(p) tr[p].l
	#define r(p) tr[p].r
	#define sum(p) tr[p].sum
	#define laz(p) tr[p].laz
}tr[2500005];

int a[500005];

void pushup(int p)
{
	sum(p) = sum(p << 1) + sum(p << 1 | 1);
}

void pushdown(int p) 
{
	if (laz(p))
	{
		laz(p << 1) += laz(p);
		laz(p << 1 | 1) += laz(p);
		sum(p << 1) += laz(p) * (r(p << 1) - l(p << 1) + 1);
		sum(p << 1 | 1) += laz(p) * (r(p << 1 | 1) - l(p << 1 | 1) + 1);
		laz(p) = 0;
	}
}

void build(int p,int l,int r)
{
	l(p) = l,r(p) = r,laz(p) = 0;
	if (l == r)
	{
		sum(p) = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(p << 1,l,mid);
	build(p << 1 | 1,mid + 1,r);
	pushup(p); 
}

void update(int p,int l,int r,int x)
{
	if (l(p) >= l && r(p) <= r)
	{
		sum(p) += x * (r(p) - l(p) + 1);
		laz(p) += x; 
		return;
	}
	pushdown(p);
	int mid = l(p) + r(p) >> 1;
	if (mid >= l) update(p << 1,l,r,x);
	if (mid < r) update(p << 1 | 1,l,r,x);
	pushup(p);
}

int query(int p,int l,int r)
{
	if (l(p) >= l && r(p) <= r) return sum(p);
	pushdown(p);
	int mid = l(p) + r(p) >> 1;
	int sum = 0;
	if (mid >= l) sum += query(p << 1,l,r);
	if (mid < r) sum += query(p << 1 | 1,l,r);
	return sum;
}

void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	build(1,1,n);
	for (int i = 1; i < n; i++)
	{
		int gv = min(query(1,i,i),n - i);
		update(1,i + 1,i + gv,1);
		update(1,i,i,-gv);
		printf("%lld ",query(1,i,i));
	}
	printf("%lld\n",query(1,n,n));
}

signed main()
{
	#ifdef USE_FREOPEN
		freopen(FILENAME ".in","r",stdin);
		freopen(FILENAME ".out","w",stdout);
	#endif
	int _ = 1;
	#ifdef MUL_TEST
		cin >> _;
	#endif
	while (_--)
		solve();
	_^=_;
	return 0^_^0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void build(long long int, long long int, long long int)’:
Main.cpp:44:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   44 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function ‘void update(long long int, long long int, long long int, long long int)’:
Main.cpp:59:24: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   59 |         int mid = l(p) + r(p) >> 1;
      |                        ^
Main.cpp: In function ‘long long int query(long long int, long long int, long long int)’:
Main.cpp:69:24: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   69 |         int mid = l(p) + r(p) >> 1;
      |                        ^

Judge Result