A. Points in Segments

An approach with a time complextiy of $ \mathcal{O}(n \times m) $ works well for small data ranges. The idea is to mark each point within the given intervals and then count how many points are not marked.

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {

    ios::sync_with_stdio(false);cin.tie(nullptr);

    int n,m;
    cin >> n >> m;
    vector<int> a(m + 1);
    int ans = 0;
    for(int i = 0;i < n;i ++){
        int x,y;
        cin >> x >> y;
        for(int j = x;j <= y;j ++){
            a[j] = 1;
        }
    }
    
    for(int i = 1;i <=m;i ++ ){
        ans += (a[i] == 0);
    }
    
    if(!ans){
        cout << 0 << endl;
    }else{
        cout << ans << endl;
        for(int i = 1;i <= m;i ++)
            cout << i << ' ';
    }

    return 0;
}

Another approach with a time complexity of $ \mathcal{O}(n + m) $ uses a prefix sum technique. Each interval updates a difference array, and a prefix sum is used to determine which points are not covered.

#include <bits/stdc++.h>

using namespace std;

int main() {
	
	int n, m;
	cin >> n >> m;
	vector<int> cnt(m + 2);
	for (int i = 0; i < n; ++i) {
		int l, r;
		cin >> l >> r;
		++cnt[l];
		--cnt[r + 1];
	}
	for (int i = 1; i <= m; ++i)
		cnt[i] += cnt[i - 1];
	
	vector<int> ans;
	for (int i = 1; i <= m; ++i) {
		if (cnt[i] == 0)
			ans.push_back(i);
	}
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it << " ";
	cout << endl;
	
	return 0;
}

B. Obtaining the String

A brute-force method with a time complexity of $ \mathcal{O}(n^3) $ can be applied when the string length is up to 50. It checks whether the characters of the two strings match and performs swaps accordingly.

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {

    ios::sync_with_stdio(false);cin.tie(nullptr);

    int n;
    cin >> n;
    string s,t;
    cin >> s >> t;

    if(s == t){
        cout << 0 << endl;
        return 0;
    }

    vector<int> numa(100),numb(100);
    for(int i = 0;i < s.size();i ++){
        numa[s[i] - 'a']++;
        numb[t[i] - 'a']++;
    }

    for(int i = 0;i <= 100;i ++){
        if(numa[i] != numb[i]){
            cout << -1 << endl;
            return 0;
        }
    }

    int ans = 0;
    vector<int> res;
    for(int i = 0;i < n - 1;i ++){
        if(s[i] == t[i]) continue;
        for(int j = i + 1;j < n;j ++){
            if(s[j] == t[i]){
                for(int k = j;k > i;k--){
                    swap(s[k],s[k - 1]);
                    ans++;
                    res.push_back(k);
                }
                break;
            }
        }
    }

    cout << ans << endl;
    for(auto i : res)
        cout << i << ' ';

    return 0;
}

An optimized version with a time complexity of $ \mathcal{O}(n^2) $ simplifies the process by directly swapping characters once the correct position is found.

#include <bits/stdc++.h>

using namespace std;

int main() {
	
	int n;
	string s, t;
	cin >> n >> s >> t;
	
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		if (s[i] == t[i]) continue;
		int pos = -1;
		for (int j = i + 1; j < n; ++j) {
			if (s[j] == t[i]) {
			        pos = j;
			        break;
			}
		}
		if (pos == -1) {
			cout << -1 << endl;
			return 0;
		}
		for (int j = pos - 1; j >= i; --j) {
			swap(s[j], s[j + 1]);
			ans.push_back(j);
		}
	}
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}

C. Songs Compression

This solution has a time complexity of $ \mathcal{O}(n \log_2 n) $. It sorts the songs based on their memory differences and attempts to compress them starting from the smallest difference.

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int,int> PII;

signed main() {

    ios::sync_with_stdio(false);cin.tie(nullptr);

    int n,m;
    cin >> n >> m;

    vector<PII> a(n);
    for(auto& [x,y] : a)
        cin >> x >> y;

    sort(a.begin(),a.end(),[](PII x,PII y){
        return x.first - x.second < y.first - y.second;
    });

    int ans = 0, now = 0;
    for(auto i : a){
        now += i.second;
    }
    if(now > m){
        cout << -1 << endl;
        return 0;
    }
    
    for(auto i : a){
        if(i.first - i.second + now <= m){
            now += i.first - i.second;
            ans ++;
        }else
            break;
    }
    cout << n - ans << endl;

    return 0;
}

D. Walking Between Houses

This approach has a time complexity of $ \mathcal{O}(k) $. It first checks if the movement is possible and then greedily moves as far as possible in each step.

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {

    ios::sync_with_stdio(false);cin.tie(nullptr);

    int n,k,s;
    cin >> n >> k >> s;

    if(s > (n - 1) * k || s < k){
        cout << "NO" << endl;
        return 0;
    }

    cout << "YES" << endl;
    int sum = 0, now = 1;
    for(; k;k-- ){
        int i = min(s - k + 1, n - 1);
        s -= i;
        if( i + now > n){
            cout << now - i << ' ';
            now -= i;
        }else {
            cout << now + i << ' ';
            now += i;
        }
    }

    return 0;
}