data structures *2000

Please click on ads to support us..

C++ Code:

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int N = 523232, lg=18;
const ll MOD = 1e9+7; // 998244353

ll getmod(ll a, ll mod=MOD)                   {return (a>=0&&a<mod ? a : ((a%mod+mod)%mod));}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}
inline ll poww(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = getmod(ans*a);
        b >>= 1;
        a = getmod(a*a);
    }
    return ans;
}

int n, A[N], P[N], Q[N], ANS[N], seg[N];

void reset() {
	for(int i=(1<<lg);i<=(1<<lg+1)-1;i++) {
		seg[i] = 1;
	}
	for(int i=(1<<lg)-1; i; --i) {
		seg[i] = seg[2*i] + seg[2*i+1];
	}
}

void update(int ind) {
	if(ind==0) {return;}
	if(ind>=(1<<lg)) {
		seg[ind] = 0;
	} else {
		seg[ind] = seg[2*ind] + seg[2*ind+1];
	}
	update(ind/2);
}

int query(int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
	if(l>=rc || lc>=r) {return 0;}
	if(l<=lc && rc<=r) {
		return seg[ind];
	}
	int mid = (rc+lc)/2;
	return query(l, r, 2*ind, lc, mid) + query(l, r, 2*ind+1, mid, rc);
}

int query2(int wh, int ind=1) {
	if(ind>=(1<<lg)) {
		return (ind-(1<<lg)+1);
	}
	if(seg[2*ind]>=wh) {return query2(wh, 2*ind);}
	return query2(wh-seg[2*ind], 2*ind+1);
}

int main () {
	ios;

	cin>>n;
	reset();
	for(int i=1; i<=n; i++) {
		cin>>P[i]; P[i]++;
		A[n-i] += query(1, P[i]);
		update(P[i]+(1<<lg)-1);
	}
	reset();
	for(int i=1; i<=n; i++) {
		cin>>Q[i]; Q[i]++;
		A[n-i]+=query(1, Q[i]);
		update(Q[i]+(1<<lg)-1);
	}
	reset();
	for(int i=1;i<=n;i++) {
		if(A[i]>i) {A[i]-=(i+1); A[i+1]++;}
	}
	for(int i=n-1;i>=0;i--) {
		ANS[n-i] = query2(A[i]+1);
		update(ANS[n-i]+(1<<lg)-1);
	}
	for(int i=1; i<=n; ++i) {
		cout<<ANS[i]-1<<' ';
	}

	return 0;
}


Comments

Submit
0 Comments
More Questions

1629D - Peculiar Movie Preferences
1629E - Grid Xor
1629F1 - Game on Sum (Easy Version)
2148. Count Elements With Strictly Smaller and Greater Elements
2149. Rearrange Array Elements by Sign
2150. Find All Lonely Numbers in the Array
2151. Maximum Good People Based on Statements
2144. Minimum Cost of Buying Candies With Discount
Non empty subsets
1630A - And Matching
1630B - Range and Partition
1630C - Paint the Middle
1630D - Flipping Range
1328A - Divisibility Problem
339A - Helpful Maths
4A - Watermelon
476A - Dreamoon and Stairs
1409A - Yet Another Two Integers Problem
977A - Wrong Subtraction
263A - Beautiful Matrix
180C - Letter
151A - Soft Drinking
1352A - Sum of Round Numbers
281A - Word Capitalization
1646A - Square Counting
266A - Stones on the Table
61A - Ultra-Fast Mathematician
148A - Insomnia cure
1650A - Deletions of Two Adjacent Letters
1512A - Spy Detected