제출 #1278902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278902		iamsazidh	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	98 ms	19892 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 = (int)s.size();
    if (n == 0) return 0;

    // pos indexed by value offset with adjust (keeps your approach).
    int adjust = n + 50;
    int SZ = (n * 2) + 100;
    vector<vector<int>> pos(SZ);
    for (int i = 0; i < n; ++i) {
        int idx = adjust + s[i];
        if (idx >= 0 && idx < SZ) pos[idx].push_back(i);
        // else: value out of window -> ignored (or handle differently)
    }

    // pointers to next candidate in each pos vector (avoid re-scanning removed positions)
    vector<int> ptr(SZ, 0);

    BIT tr(n);
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        if (tr.ask(i, i) == 0) continue; // i already removed

        int key = adjust - s[i];        // we look for value == -s[i] originally
        if (key < 0 || key >= SZ) continue; // no such bucket

        auto &vec = pos[key];
        int pidx = ptr[key];

        // advance pointer to first vec[pidx] > i
        while (pidx < (int)vec.size() && vec[pidx] <= i) ++pidx;
        // advance pointer further if that position already removed
        while (pidx < (int)vec.size() && tr.ask(vec[pidx], vec[pidx]) == 0) ++pidx;

        // store back pointer
        ptr[key] = pidx;
        if (pidx >= (int)vec.size()) continue; // no valid partner

        int p = vec[pidx];
        if (p <= i) continue; // just in case, safety

        // valid pair (i, p)
        ans += tr.ask(i+1, p-1);
        if (s[i] > 0) ans++;
        tr.remove(p);
        tr.remove(i);

        // advance pointer since we removed vec[pidx]
        ++ptr[key];
    }

    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