AOJ 2374 : RabbitLunch

解法

sort+累積和+setで解こうとするとsetのメモリの定数倍が大きくMLEするので、
尺取法みたいな感じ(？)で次数を1つずつ順に見ながら、最小カットを考えるとO(n)で解けて、メモリも足りる。

#include <iostream>
using namespace std;
typedef long ll;
#define N 2500001
int x[N], y[N], x2[N], y2[N];

int main(){
	int n, m, b, d;
	cin>>n>>m>>x[0]>>b>>y[0]>>d;
	ll res = x[0];
	x2[0] = 1;
	y2[n+1] = 1;
	x2[x[0]]++;
	for(int i = 1; i < n; i++){
		x2[x[i]=(58*x[i-1]+b)%(m+1)]++;
		res += x[i];
	}
	y2[y[0]]++;
	for(int i = 1; i < m; i++){
		y2[y[i]=(58*y[i-1]+d)%(n+1)]++;
	}
	ll sum = res, pos = m, pos2 = 0, cnt = 0, cnt2 = m;
	while(x2[pos]==0) pos--;
	while(y2[pos2]==0) pos2++;
	while(pos>0){
		sum -= pos;
		cnt++;
		x2[pos]--;
		while(x2[pos]==0) pos--;
		while(cnt2 && cnt >= pos2){
			sum += pos2;
			cnt2--;
			y2[pos2]--;
			while(y2[pos2]==0) pos2++;
		}
		if(res>sum+cnt*cnt2) res = sum+cnt*cnt2;
	}
	cout<<res<<endl;
	
	return 0;
}

MLEする方

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef long ll;
#define N 2500000
set<int> st;
int x[N], y[N];

int main(){
	int n, m, a, b, c, d;
	cin>>n>>m>>a>>b>>c>>d;
	x[0] = a;
	for(int i = 1; i < n; i++) x[i] = (58*x[i-1]+b)%(m+1);
	sort(x, x+n);
	y[0] = c;
	for(int i = 1; i < m; i++) y[i] = (58*y[i-1]+d)%(n+1);
	sort(y, y+m);
	for(int i = m-1; i > 0; i--) y[i]-=y[i-1];
	st.insert(-1);
	st.insert(m);
	for(int i = 0; i < m; i++)
		if(y[i]) st.insert(i);
	ll res = 0;
	for(int i = n-1; i >= 0; i--){
		int deg = x[i];
		auto it = st.lower_bound(m-deg);
		int num = *it;
		if(num < m){
			if(--y[num] == 0) st.erase(it);
		}
		int deg2 = deg-m+num;
		if(deg2){
			auto it2 = st.lower_bound(m-deg);
			--it2;
			num = *it2;
			if(num >= 0){
				if(--y[num] == 0) st.erase(it2);
				if(y[num+deg2]++ == 0) st.insert(num+deg2);
				deg2 = 0;
			}
		}
		res += deg-deg2;
	}
	cout<<res<<endl;
	
	return 0;
}