Posted in Two Pointers

CF 580B Kefa and Company

5/20/2017
Problem: http://codeforces.com/problemset/problem/580/B
Solution: Sort all friends according to their money, then use prefix sum and two
pointers to get the maximum sum within the range.


#include<iostream>
#include<algorithm>
using namespace std;

struct T{
	int m;
	int s;
};

bool cmp(T a, T b) {
	return a.m < b.m;
} 

int main () {
	int n, d;
	cin >> n >> d;
	T a[100005]; 
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].m >> a[i].s;
	} 
	long long ans = 0;
	sort(a + 1, a + n + 1, cmp);
	long long sum[100005] = {0};
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + a[i].s;
		//cout << sum[i] << ' ';
	} 
	int l = 1, r = 1;
	long long ma = 0;
	while (l <= n) {
		while (a[r].m - a[l].m < d && r <= n) {
			r ++; 
		} 
		r--; 
		ma = max(sum[r] - sum[l - 1], ma);
		//cout << l << ' ' << r << endl; 
		//cout << sum[r - 1] << ' ' << sum[l - 1] << endl; 
		l++; 
	}
	cout << ma;
	return 0; 
}

Posted in Two Pointers

CF 567C Geometric Progression

7/4/2017
Problem: http://codeforces.com/problemset/problem/567/C
Solution: This is a rather exquisite solution. Two map, l, r are applied to
record the number of numbers on the left/right side of the current one
pointed.



#include<iostream>
#include<map>
using namespace std;
long long a[200005] = {0};
map<long long, long long> l, r;

int main() {
	int n, k;
	long long ans = 0;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		r[a[i]]++;
	}
	for (int i = 1; i <= n; i++) {
		long long ll = 0, rr = 0;
		if (a[i] % k == 0) {
			ll = l[a[i] / k];
		}
		r[a[i]]--; 
		rr = r[a[i] * k];
		ans += ll * rr;
		l[a[i]]++;
	}
	cout << ans;
	return 0;
}

Posted in Two Pointers

CF 279B Books

5/21/2017
Problem: http://codeforces.com/problemset/problem/279/B
Solution: prefix sum, two pointer
Note: Pay attention to the case that r < l after l++

#include<iostream>
using namespace std;

int main() {
int n, t;
cin >> n >> t;
int a[100005] = {0};
long long sum[100005] = {0};
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i – 1] + a[i];
}
int l = 1, r = 1;
int m = 0;
while (r <= n && l <= r) {
while (sum[r] – sum[l – 1] <= t && r <= n) {
r ++;
}
r–;
// cout << l << ' ' << r << endl;
m = max(m, r – l + 1);
l ++;
if (r < l) {
r = l;
}
}
cout << m;
return 0;
}