CompetitiveProgramming/codeforces/100418/H.cpp at master · phonglnDEV/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)

#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A,n)  { cout << #A << " = "; FOR(_,1,n) cout << A[_] << ' '; cout << endl; }
#define PR0(A,n) { cout << #A << " = "; REP(_,n) cout << A[_] << ' '; cout << endl; }

#define sqr(x) ((x) * (x))
#define ll long long
#define SZ(x) ((int) (x).size())
using namespace std;

const int MN = 1000111;
const ll MOD = 1e9 + 7;
int n;
ll k[MN], a[MN];

int read() {
	int x; assert(scanf("%d", &x));
	return x;
}

ll sum1(ll n) {
	return (n * (n + 1) / 2) % MOD;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
	while (scanf("%d", &n) == 1) {
		ll suma = 0, sumk = 0;
		FOR(i,1,n) {
			k[i] = read();
			a[i] = read();

			suma += a[i] * k[i];
			sumk += k[i];
		}
		ll each = suma / sumk;
//		DEBUG(each);

		ll res = 0, less = 0, more = 0;
		FOR(i,1,n) {
			if (a[i] == each) {
				res = (res + less % MOD * k[i]) % MOD;
				res = (res + more % MOD * k[i]) % MOD;
			}
			else if (a[i] < each) {
//				cout << "a[i] < each" << endl;
				ll delta = each - a[i];
				ll need = delta * k[i];
				ll can = min(more, need);

				if (can == need) {
					res = (res + sum1(k[i]) * delta) % MOD;
				}
				else {
					ll lastFullCol = can / delta;
					ll lastColHeight = can % delta;

					// move to left
					res = (res + sum1(lastFullCol) * delta) % MOD;
					res = (res + (lastFullCol + 1) * lastColHeight) % MOD;
//					DEBUG(res);

					// move to right
					if (k[i] > lastFullCol + 1) {
						ll dist = k[i] - (lastFullCol + 2);
						res = (res + sum1(dist) * delta) % MOD;
					}
					res = (res + (delta - lastColHeight) * (k[i] - lastFullCol - 1)) % MOD;
				}

				more -= can;
				need -= can;

				res = (res + more % MOD * k[i]) % MOD;
				res = (res + less % MOD * k[i]) % MOD;

				less += need;
			}
			else { // a[i] > each
//				cout << "a[i] > each" << endl;
				ll delta = a[i] - each;
				ll need = delta * k[i];
				ll can = min(less, need);

				if (can == need) {
					res = (res + sum1(k[i]) * delta) % MOD;
				}
				else {
					ll lastFullCol = can / delta;
					ll lastColHeight = can % delta;

					// move to left
					res = (res + sum1(lastFullCol) * delta) % MOD;
					res = (res + (lastFullCol + 1) * lastColHeight) % MOD;
//					DEBUG(res);

					// move to right
					if (k[i] > lastFullCol + 1) {
						ll dist = k[i] - (lastFullCol + 2);
						res = (res + sum1(dist) * delta) % MOD;
					}
					res = (res + (delta - lastColHeight) * (k[i] - lastFullCol - 1)) % MOD;
				}

				less -= can;
				need -= can;

				res = (res + more % MOD * k[i]) % MOD;
				res = (res + less % MOD * k[i]) % MOD;

				more += need;
			}
			assert(more == 0 || less == 0);
//			DEBUG(res);
		}
		cout << res << endl;
	}
}