记录编号	172918	评测结果	AAAAAAAAAAA
题目名称	[USACO Nov13]空牛栏	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	1.811 s
提交时间	2015-07-27 16:22:44	内存使用	23.20 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <fstream>

using namespace std;

#define int long long
inline int qrd(), f(int, int, int);
const int MAXK(10001), MAXN(3000001);
int n, k, ans = 0, cnt = 0, rm[MAXN] = {-1};

main()
{
	freopen("empty.in", "r", stdin);
	ofstream fout("empty.out");
#define cout fout
	n = qrd();
	k = qrd();
	fill(rm, rm + n + 1, -1);
	int x, y, a, b;
	for (int i = 1; i <= k; ++i){
		x = qrd();
		y = qrd();
		a = qrd();
		b = qrd();
		
		for (int j = 1; j <= y; ++j)
			rm[f(a, j, b)] += x;
	}
	while (ans <= 2 * n - 1){
		if (cnt > 0 && rm[ans % n] < 0){
			cnt += rm[ans % n];
			rm[ans % n] = 0;
		}
		else if (rm[ans % n] > 0){
			cnt += rm[ans % n];
			rm[ans % n] = 0;
		}
		if(cnt == 0 && ans >= n && rm[ans % n] == -1){
			cout << ans % n;
			return 0;
		}
		ans++;
	}
	cout << -1;
}

inline int qrd(){
	int x = 0;
	char c;
	while (! isdigit(c = getchar()));
	while (isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x;
}

inline int f(int a, int i, int b){
	return (((a * i) % n) + (b % n)) % n;
}