Submission #63562058

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>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m;
int a[N], k[N];
vector <int> tag[N];
struct BIT {
  int tree[N<<4];
  int tag[N<<4];
#define mid ((l+r)/2)
#define ls (x<<1)
#define rs (x<<1|1)
  inline void pushdown (int x) {
    tag[ls]+=tag[x],tag[rs]+=tag[x];
    tree[ls]+=tag[x],tree[rs]+=tag[x];
    tag[x] = 0;
    return ;
  }
  inline void update(int x, int l, int r, int L, int R, int d) {
    if(L>R) return ;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m;
int a[N], k[N];
vector <int> tag[N];
struct BIT {
	int tree[N<<4];
	int tag[N<<4];
#define mid ((l+r)/2)
#define ls (x<<1)
#define rs (x<<1|1)
	inline void pushdown (int x) {
		tag[ls]+=tag[x],tag[rs]+=tag[x];
		tree[ls]+=tag[x],tree[rs]+=tag[x];
		tag[x] = 0;
		return ;
	}
	inline void update(int x, int l, int r, int L, int R, int d) {
		if(L>R) return ;
		if(l>=L&&r <= R) {
			tree[x]+=d;
			tag[x]+=d;
			return ;
		}
		pushdown(x);
		if(L<=mid)update(ls,l,mid,L,R,d);
		if(R>mid)update(rs,mid+1,r,L,R,d);
		tree[x]=tree[ls]+tree[rs];
		return ;
	}
	inline int query (int x, int l, int r, int L, int R) {
		if(L>R) return 0;
		if(l>=L&&r <= R) {
			return tree[x];
		}
		pushdown(x);
		int ans=0;
		if(L<=mid) ans+=query(ls,l,mid,L,R);
		if(R>mid) ans+=query(rs,mid+1,r,L,R);
		return ans;
	}
} T,T1;
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int ans=0;
	for(int i =1; i<=n; ++i) {
		cin>>a[i];
		++a[i];
		int d=T.query(1,1,N-2, a[i] + 1, N - 2);
		T1.update(1,1, N-2, i, i, d);
		ans+=d;
		tag[a[i]].push_back(i),T.update(1,1,N-2,a[i],a[i],1);
	}
	cout<<T1.query(1,1,N-2,1,n) <<"\n";
	for (int i=1; i<m; ++i) {
		int cnt = 0, siz = tag[m - i+1].size();
		for(auto v:tag[m-i+1]) {
			T1.update (1, 1, N-2, v + 1, n, -1);
			int d = T1.query(1,1,N-2, v,v);
			T1.update(1, 1, N-2, v, v, -d);
			T1.update(1, 1, N-2, v, v, v - 1 - cnt);
			++ cnt;
		}
		cout<<T1.query(1,1,N-2,1,n) <<"\n";
	}
	return 0;
}
/*
0 4 0 1 2
*/

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:61:30: warning: unused variable ‘siz’ [-Wunused-variable]
   61 |                 int cnt = 0, siz = tag[m - i+1].size();
      |                              ^~~

Judge Result