The criterion shows that we can only use either vertical segments or horizontal segments.
Since there is no limit on the segments' length, we can see that it's always optimal to use a segment with infinite length (or may be known as a line).

We can see that the vertical line x = a will span through every alarm clocks standing at positions with x-coordinate being equal to a. In a similar manner, the horizontal line y = b will span through every alarm clocks standing at positions with y-coordinate being equal to b.

So, if we use vertical lines, the number of segments used will be the number of distinct values of x-coordinates found in the data. Similarly, the number of horizontal segments used will be the number of distinct values of y-coordinates found.

The process can be implemented by a counting array, or a map.

Time complexity: for regular arrays, or for maps.

Submission link: 48211481

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n; cin >> n;
	
	map<int, int> cntx, cnty;
	
	while (n--) {
	    int x, y;
		cin >> x >> y;
		cntx[x]++; cnty[y]++;
	}
	
	cout << min(cntx.size(), cnty.size()) << endl;
	
	return 0;
}

Submission link: 48211597

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n; cin >> n;
	
	vector<int> cntx(101, 0);
	vector<int> cnty(101, 0);
	
	while (n--) {
	    int x, y;
		cin >> x >> y;
		cntx[x]++; cnty[y]++;
	}
	
	int distinctx = 0, distincty = 0;
	for (int i=0; i<101; i++) {
	    distinctx += (cntx[i] > 0);
	    distincty += (cnty[i] > 0);
	}
	
	cout << min(distinctx, distincty) << endl;
	
	return 0;
}

From the constraints given, for the i-th song, provided there exists corresponding x_i and y_i values, then the following inequality must hold: 2 ≤ x_i + y_i ≤ 2·a_i.
Thus, if any b_i is either lower than 2 or higher than 2·a_i, then no x_i and y_i can be found, thus, Sereja's joy will surely decrease by 1.

Amongst all pairs of that x_i + y_i = b_i, the pair with the highest value of x_i·y_i will be one with the equal value of x_i = y_i (this can be proven by the famous AM-GM inequality).
Thus, if b_i is divisible by 2, we can easily pick .
Also, from this, we can see (either intuitively or with static proofs) that the lower the difference between x_i and y_i is, the higher the value x_i·y_i will be. Thus, in case b_i being odd, the most optimal pair will be or (the order doesn't matter here).

Time complexity: .

Submission link: 48212208

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n; cin >> n;
	
	vector<int> a(n), b(n);
	for (auto &z: a) cin >> z;
	for (auto &z: b) cin >> z;
	
	long long Joy = 0;
	for (int i=0; i<n; i++) {
		if (b[i] < 2 || b[i] > a[i] * 2) {Joy--; continue;}
		int x = b[i] / 2, y = b[i] - x;
		Joy += 1LL * x * y;
	}
	cout << Joy << endl;
	
	return 0;
}

The query content looks pretty confusing at first, to be honest.
Since k is static throughout a scenario, we can group the boxes into k groups, the z-th box (in this editorial let's assume that the indices of the boxes start from 0) falls into group number .

Then, each query can be simplified as this: "Is that true that among the boxes with numbers from l_i to r_i, inclusive, the candies lie only in boxes of group ?

To make sure the answer for a query being "Yes", Dima has to remove candies from all candied-box in all groups other than , while in that exact group, fill every empty box with a candy. Obviously, we'll consider boxes with indices between l_i and r_i inclusively only.

We can make k lists, the t-th (0-indexed) list stores the indices of candied boxes in group t.

We'll process with each query as the following:

• Obviously, given from the criteria, each range will consist of exactly boxes per each group. Let's denote .
• Traverse all groups, for the t-th group (again, 0-indexed), let's denote x_t as the number of candied boxes of group t in the given range. This value can be calculated quickly through binary searching the constructed lists above.
• If group t is not the group being demanded to have candies (group ), we'll need to perform x_t actions (removing candies). Otherwise, we'll need to perform A - x_t actions (adding candies to empty boxes).

Time complexity: .

Submission link: 48212838

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n, k, w; string s;
	cin >> n >> k >> w >> s;
	
	vector< vector<int> > CandyModulo(k);
	
	for (int i=0; i<n; i++) {
	    if (s[i] == '0') continue;
	    CandyModulo[i % k].push_back(i);
	}
	
	while (w--) {
	    int l, r;
		cin >> l >> r; l--; r--;
		
		int res = 0;
		int demandedGroup = (l + k - 1) % k;
		int BoxesPerGroup = (r - l + 1) / k;
		
		for (int id=0; id<k; id++) {
		    
			int x = lower_bound(CandyModulo[id].begin(), CandyModulo[id].end(), l) - CandyModulo[id].begin();
			int y = upper_bound(CandyModulo[id].begin(), CandyModulo[id].end(), r) - CandyModulo[id].begin();
			
			if (id == demandedGroup) {
			    res += (BoxesPerGroup - (y - x));
			}
			else res += (y - x);
		}
		
		cout << res << endl;
	}
	
	return 0;
}

...

Submission link: 1010182

...

Submission link: 1010182