제출 #1278908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278908		iamsazidh	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	93 ms	36412 KiB

shoes

//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

typedef long long              ll;
typedef double                 dl;
typedef vector<int>            vi;
typedef vector<vector<int>>    vii;
typedef vector<ll>             vl;
typedef vector<bool>           vb;
typedef pair<int,int>         pii;
typedef pair<ll, ll>          pll;

#define ff                first
#define ss                second
#define all(a)            a.begin(),a.end()
#define gcd(a,b)          __gcd(a,b)
#define lcm(a,b)          (a*(b/gcd(a,b)))
#define file();           freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define flush             fflush(stdout);
#define spc               " "

#ifdef ONLINE_JUDGE
	#define debarr(array)
	#define deb(x)
	#define del
	#define debug(...)
#else
	#define debarr(array)  for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
	#define deb(x)         cerr << #x << " = " << x << endl;
	#define del cerr << '\n';
#endif


const double PI =         acos(-1);
const int MOD =           1000000007;
const int inf =           (2147483647);
const double EPS =        1e-6;
const int MAXN =          1e5+10;




class BIT{
	private:
		vector<int> tr; int n;
	public:
	 	int lsb(int x){
			return (x & -x);
		}
		BIT(int _n){
			n = _n;
			tr.resize(n+1, 1); //all are 1 s first
			for(int i = 1; i <= n; i++){
				if(i+lsb(i)<=n) tr[i+lsb(i)] += tr[i];
			}
		}
		int till(int x){
			int ans = 0;
			while(x>0){
				ans += tr[x];
				x -= lsb(x);
			}
			return ans;
		}
		int ask(int l, int r){
			l++, r++; // queries are 0 index based
			if(l>r) return 0;
			return till(r)-till(l-1);
		}
		void remove(int x){
			x++;
			while(x<=n){
				tr[x] -= 1;
				x += lsb(x);
			}
			return;
		}
};

long long count_swaps(std::vector<int> s) {
	int n = s.size();
	vii pos((n*5)+100);
	int adjust = ((n*5)+100)/2;
	ll ans = 0;
	for(int i = 0; i < n; i++){
		pos[adjust+s[i]].push_back(i);
	}
	vector<int> ptr(n*5+100, 0);
	BIT tr(n);
	for(int i = 0; i < n; i++){
		if(tr.ask(i, i)==0) continue;
		int key = adjust-s[i];
		int p = ptr[key];
		while(pos[key][p]<=i) p++;
		while(tr.ask(pos[key][p], pos[key][p])==0) p++;
		ans += tr.ask(i+1, pos[key][p]-1);
		if(s[i]>0) ans ++;
		tr.remove(pos[key][p]);
		tr.remove(i);
		ptr[key] = p+1;
	}





	return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15