2022 CCPC Weihai Site

比赛地址 ：Codeforces Gym 104023

待补：HLM

A - Duna

签到题。答案是五个位置各自的人数和那过冠军的人数的 \(\min\) 。

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
#include <bits/stdc++.h>
using namespace std;

#define N 10007

inline int getid() {
	static string s;
	static int totid;
	static map<string, int> id;
	cin >> s;
	if (!id[s]) id[s] = ++totid;
	return id[s];
}

bool champ[N];

int cnt[6], tot;

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j <= 5; ++j) champ[getid()] = true;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int id = getid(), pos; cin >> pos;
		tot += champ[id]; cnt[pos]++; 
	}
	for (int i = 1; i <= 5; ++i) tot = min(tot, cnt[i]);
	printf("%d\n", tot);
	return 0;
}

B - Recruitment

有一个长度为 \(n\) 的序列，初始由加号连接。每次把一个加号改成乘号，到最后全部变为乘号，一共有 \(n\) 个表达式。

给定 \(n\) 个表达式的结果 \((s_i\le 10^9)\) ，构造初始序列和修改过程。

注意到最后的值就是全部的乘积，所以不是 \(1\) 的数字个数最多只有 \(30\) 个。

注意到把 \(+1\) 变成 \(\times 1\) 会让结果变小，且此条件是充要条件，所以先把所有的 \(1\) 找出来，放到最后。

然后缩减数列，只会剩下 \(30\) 个，最后一个数就是所有的乘积，然后倒着每次尝试分解，搜索分解的树结构即可。

错误 1： \(2+2=2\times 2\) 所以缩减数列的时候不能简单的判断相邻不同

错误 2： 在 auto 遍历 STL 的时候不能修改，所以不能在循环中修改数集 / 将数集传引用来 dfs 导致被修改 。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define fr first
#define sc second
#define mp make_pair
#define pb push_back

#define N 100007

bool del[N];

int a[N], res[N], op[N];

int A, B;

inline bool check(int n, int dlt) {
	int lim = sqrt(n);
	for (int i = 1; i <= lim; ++i)
		if (n % i == 0) 
			if (n - i - n / i == dlt) {A = i; B = n / i; return true;}
	return false;
}

int nodecnt, totlim;

struct node {int ls = 0, rs = 0, x = 0, tim = 0;} c[N];

map<multiset<int>, bool> vis;

pii lim[N];

bool dfs(int p, set<int> leaf, multiset<int> val) {
	if (vis[val]) return false;
	set<int> nxtleaf = leaf;
	multiset<int> nxtval = val;
	vis[val] = true;
	if (p == totlim + 1) return true;
	for (auto x : leaf) {
		if (check(c[x].x, lim[p].fr)) {
			nxtleaf.erase(x);
			nxtval.erase(nxtval.lower_bound(c[x].x));
			c[x].tim = lim[p].sc;
			c[c[x].ls = ++nodecnt].x = A;
			c[c[x].rs = ++nodecnt].x = B;
			nxtleaf.insert(nodecnt - 1); 
			nxtleaf.insert(nodecnt);
			nxtval.insert(A); 
			nxtval.insert(B);
			if (dfs(p + 1, nxtleaf, nxtval)) return true;
			nxtval.erase(nxtval.lower_bound(c[nodecnt].x));
			nxtval.erase(nxtval.lower_bound(c[nodecnt - 1].x));
			nxtleaf.erase(nodecnt);
			nxtleaf.erase(nodecnt - 1);
			c[x].tim = c[x].ls = c[x].rs = 0;
			nodecnt -= 2;
			nxtval.insert(c[x].x);
			nxtleaf.insert(x);
		} 
	}
	return false;
}

int id = 0;

void build(int u) {
	if (!c[u].ls) {res[++id] = c[u].x; return;}
	build(c[u].ls);
	op[c[u].tim] = id; 
	build(c[u].rs);
}

int main() {
	int n = rd();
	for (int i = 1; i <= n; ++i) a[i] = rd();
	int tot = n, cnt1 = 0;
	for (int i = n - 1; i; --i) 
		if (a[i] > a[i + 1]) {del[i] = true; ++cnt1; res[tot--] = 1; op[i] = tot;}
	for (int i = 1; i <= n; ++i) 
		if (i < n && a[i] > a[i + 1]) {a[i] -= cnt1; --cnt1;}
		else a[i] -= cnt1;
	c[nodecnt = 1].x = a[n];
	for (int i = n - 1; i; --i)   
		if (!del[i]) lim[++totlim] = make_pair(a[i + 1] - a[i], i);
	if (!dfs(1, set<int>{1}, multiset<int>{a[n]})) {puts("-1"); return 0;}
	build(1);
	for (int i = 1; i <= n; ++i) printf("%d ", res[i]); puts("");         
	for (int i = 1; i < n; ++i) printf("%d\n", op[i]);
	return 0;
}

C - Grass 5

给定 \(n\) 个点，问能否选五个点 \(ABCDE\) 使得 \(BCDE\) 和 \(A\) 构成的线段两两只交在 \(A\) 。

玩一下发现只要不共线总能找到解，于是找到不共线的五个点之后暴力枚举答案。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define fr first
#define sc second
#define mp make_pair
#define pb push_back

#define N 25007

#define letp const P

struct P {
	ll x, y;
	P operator - (letp &p) const {return {x - p.x, y - p.y};}
	ll operator | (letp &p) const {return x * p.x + y * p.y;} // dot
	ll operator ^ (letp &p) const {return x * p.y - y * p.x;} // cross
} a[N], p[6];

inline void work() {
	int n = rd();
	for (int i = 1; i <= n; ++i) {a[i].x = rd(); a[i].y = rd();}
	if (n <= 4) {puts("NO"); return;}
	int tot = 2;
	p[1] = a[1]; p[2] = a[2];
	bool fl = false;
	for (int i = 3; i <= n && tot < 5; ++i) 
		if (fl || tot < 4) {
			p[++tot] = a[i];
			if (((p[i] - p[1]) ^ (p[2] - p[1])) != 0) fl = true;
		} else if (((a[i] - p[1]) ^ (p[2] - p[1])) != 0) {
			fl = true; p[++tot] = a[i];
		}
	if (tot < 5) {puts("NO"); return;}
	puts("YES");
	for (int i = 1; i <= 5; ++i) {
		bool fl = true;
		for (int j = 1; j <= 5; ++j)
			if (j != i) for (int k = 1; k <= 5; ++k)
				if (k != i && k != j) 
					if (((p[k] - p[i]) ^ (p[j] - p[i])) == 0 && ((p[k] - p[i]) | (p[j] - p[i])) >= 0) {
						fl = false; break;
					}
		if (fl) {
			printf("%lld %lld\n", p[i].x, p[i].y);
			for (int j = 1; j <= 5; ++j)
				if (j != i) printf("%lld %lld\n", p[j].x, p[j].y);
			return;
		}
	}

}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

D. Sternhalma

胖胖说是签到题。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5,maxs=1<<19;

int te,num[maxn+5];char s[maxn+5][maxn+5];
int pic[maxn+5][maxn+5],cnt,ID[maxn+5][maxn+5];
int m,SA[maxs+5],f[maxs+5],si[maxs+5];

int getop() {char ch=getchar();while (ch!='.' && ch!='#') ch=getchar();return ch=='#';}
void Fix(int &x,int y) {if (y>x) x=y;}
int gettl(int x,int y){
	if (num[x]>num[x-1]) return ID[x-1][y-1];
	else return ID[x-1][y];
}
int gettr(int x,int y){
	if (num[x]>num[x-1]) return ID[x-1][y];
	else return ID[x-1][y+1];
}
int getl(int x,int y) {return ID[x][y-1];}
int getr(int x,int y) {return ID[x][y+1];}
int getdl(int x,int y){
	if (num[x]>num[x+1]) return ID[x+1][y-1];
	else return ID[x+1][y];
}
int getdr(int x,int y){
	if (num[x]>num[x+1]) return ID[x+1][y];
	else return ID[x+1][y+1];
}
inline bool cmp(const int &i,const int &j) {return si[i]<si[j] || si[i]==si[j] && i<j;}
int main(){
	memset(ID,255,sizeof(ID));
	num[1]=3;num[2]=4;num[3]=5;num[4]=4;num[5]=3;
	for (int i=1;i<=5;i++)
		for (int j=1;j<=num[i];j++)
			scanf("%d",&pic[i][j]),ID[i][j]=cnt++;
	memset(f,192,sizeof(f));
	f[0]=0;
	for (int i=1;i<maxs;i++) SA[++m]=i,si[i]=si[i>>1]+(i&1);
	sort(SA+1,SA+1+m,cmp);
	for (int k=1,i=SA[k];k<maxs;k++,i=SA[k])
		for (int x=1;x<=5;x++)
			for (int y=1;y<=num[x];y++)
				if (i>>ID[x][y]&1){
					Fix(f[i],f[i^(1<<ID[x][y])]);
					int tl=gettl(x,y),tr=gettr(x,y);
					int dl=getdl(x,y),dr=getdr(x,y);
					int l=getl(x,y),r=getr(x,y);
					if (tl>=0 && dr>=0)
						if ((i>>tl&1)+(i>>dr&1)==1)
							Fix(f[i],f[i^(1<<tl)^(1<<ID[x][y])^(1<<dr)]+pic[x][y]);
					if (l>=0 && r>=0)
						if ((i>>l&1)+(i>>r&1)==1)
							Fix(f[i],f[i^(1<<l)^(1<<ID[x][y])^(1<<r)]+pic[x][y]);
					if (tr>=0 && dl>=0)
						if ((i>>tr&1)+(i>>dl&1))
							Fix(f[i],f[i^(1<<tr)^(1<<ID[x][y])^(1<<dl)]+pic[x][y]);
				}
	for (scanf("%d",&te);te;te--){
		int S=0;
		for (int i=1;i<=5;i++)
			for (int j=1;j<=num[i];j++)
				S|=getop()<<ID[i][j];
		printf("%d\n",f[S]);
	}
	return 0;
}

E. Python Will be Faster than C++

签到题，发现 \(a_{n+i} = a_n + (a_n-a_{n-1})i\) ，然后简单分类讨论一下。

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
#include <bits/stdc++.h>
using namespace std;

#define N 1000

int a[N];

int main() {
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (a[i] < k) {
			printf("Python 3.%d will be faster than C++\n", i);
			return 0;
		}
	}
	int add = a[n] - a[n - 1];
	if (add >= 0) puts("Python will never be faster than C++");
	else {
		k = a[n] - k; add = -add;
		int ans = k / add;
		while (ans * add <= k) ++ans;
		printf("Python 3.%d will be faster than C++", n + ans); return 0;
	}
	return 0;
}

F. Mooncake Delivery

注意到路径中每次换颜色必定会把上一段颜色的权值全部收回，所以答案是（每一段权值+下一段起点权值）的 \(\max\) 。

所以其实有两幅图，先跑一遍 floyd ，路径权值为边权的加法，得到每一段颜色相同的权值；

然后再枚举（起点 A，终点B，下一个颜色起点C）建出 A 到 C 新的边，再跑一遍 floyd ，路径权值为边权的 \(\max\) 。

最后再考虑上路径最后一段颜色相同的即可。所有过程复杂度均为 \(\mathcal{O}(n^3)\) 。

错误 1： 因为路径可能只有一段，所以第二幅图要设置一下自己到自己距离为 \(0\) 。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

#define rep(i, x, y) for(int (i) = (x); (i) <= (y); ++(i))
#define per(i, x, y) for(int (i) = (x); (i) >= (y); --(i))

template<typename T>
inline bool getmin(T &a, T b) {return a > b ? (a = b, true) : false;}

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 307
#define inf 4000000000000000000ll

bool e[N][N];

int col[N], w[N];

ll dis[N][N], mx[N][N], ans[N][N];

inline void work() {
    int n = rd(), m = rd();
    rep(i, 1, n) rep(j, 1, n) {e[i][j] = false; mx[i][j] = dis[i][j] = inf;}
    rep(i, 1, n) col[i] = rd();
    rep(i, 1, n) {w[i] = rd(); mx[i][i] = dis[i][i] = 0;}
    rep(i, 1, m) {
        int u = rd(), v = rd(); 
        e[u][v] = e[v][u] = true; 
        dis[u][v] = w[v]; dis[v][u] = w[u];
    }
    // floyd for same color
    rep(k, 1, n) rep(u, 1, n) rep(v, 1, n) getmin(dis[u][v], dis[u][k] + dis[k][v]);
    rep(u, 1, n) rep(v, 1, n) dis[u][v] += w[u];
    // new graph : a path of same color points + an another color point
    rep(u, 1, n) rep(k, 1, n) 
        if (col[u] == col[k]) rep(v, 1, n)
            if (col[k] != col[v] && e[k][v]) getmin(mx[u][v], dis[u][k] + w[v]);
    // floyd on new graph
    rep(k, 1, n) rep(u, 1, n) rep(v, 1, n) getmin(mx[u][v], max(mx[u][k], mx[k][v]));
    // consider adding a path of same color in the end
    rep(u, 1, n) rep(v, 1, n) {
        ans[u][v] = mx[u][v];
        rep(k, 1, n) if (col[v] == col[k]) getmin(ans[u][v], max(mx[u][k], dis[k][v]));
    }
    rep(u, 1, n) {
        rep(v, 1, n) printf("%lld ", ans[u][v]);
        puts("");
    }
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

G. Grade 2

给定 \(x\) ，多次询问 \([l,r]\) ，计算 \(\sum_{k=l}^r[\operatorname{gcd}(k x \oplus x, x)=1]\)

柴老师发现循环节是 \(2^{\lceil \log_2 x\rceil}\) ，遂暴力（做差不用讨论写法很简单）。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
	ll x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 10000007

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

int sum[N];

int main() {
	int x = rd(), n = rd();
	int period = 2 << __lg(x);
	for (int i = 0; i < period; ++i) 
		sum[i] = sum[i - 1] + (gcd((1ll * i * x) ^ x, x) == 1ll);
	auto calc = [&](ll p) {
		return sum[period - 1] * (p / period) + sum[p % period];
	};
	for (int i = 1; i <= n; ++i) {
		ll l = rd(), r = rd();
		printf("%lld\n", calc(r) - calc(l - 1));
	}
	return 0;
}

I. Dragon Bloodline

胖胖做的，贪心 + 卡常。

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
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=50000,LOG=20;

int te,n,m;
LL a[maxn+5],b[LOG+5],sum;
LL now[maxn+5],tem[LOG+5];
int K,ID[maxn+5];

inline bool cmp(const int &i,const int &j) {return now[i]>now[j] || now[i]==now[j] && i>j;}
bool check(LL mid){
	for (int i=0;i<=LOG;i++) tem[i]=b[i];
	for (int i=1;i<=n;i++) now[i]=a[i]*mid;
	for (int j=LOG;j>=0;j--){
		for (int i=1;i<=n && tem[j];i++)
			if (now[i]>=(1LL<<j)){
				LL cnt=min(now[i]>>j,tem[j]);
				now[i]-=cnt<<j;
				tem[j]-=cnt;
			}
		if (!tem[j]) continue;
		K=0;for (int i=1;i<=n;i++) if (now[i]) ID[++K]=i;
		if (K<=tem[j]) return true;
		nth_element(ID+1,ID+tem[j],ID+K+1,cmp);
		LL lim=now[ID[tem[j]]];int y=ID[tem[j]];
		// printf("[%d]\n",tem[j]);
		int cnt=0;
		for (int i=1;i<=K;i++)
			if (now[ID[i]]>lim || now[ID[i]]==lim && ID[i]>=y) now[ID[i]]=0,cnt++;
		// printf("[%d]\n",cnt);
	}
	for (int i=1;i<=n;i++) if (now[i]) return false;
	return true;
}
int main(){
	for (scanf("%d",&te);te;te--){
		scanf("%d%d",&n,&m);
		LL L=0,R=0;sum=0;
		for (int i=1;i<=n;i++) scanf("%lld",&a[i]),R=max(R,a[i]);
		for (int i=0;i<=LOG;i++) b[i]=0;
		for (int i=0;i<m;i++) scanf("%lld",&b[i]),sum+=b[i]<<i;
		R=sum/R;
		for (LL mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
			check(mid)?L=mid+1:R=mid-1;
		printf("%lld\n",R);
	}
	return 0;
}

J. Eat, Sleep, Repeat

给定 \(n\) 个数 \(a_1, a_2,\dots, a_n\) ，两人博弈每次可以让一个数字 \(-1\) 。

有若干限制 \(lim_{x_i}=y_i\) 表示集合中任意时刻 \(x_i\) 出现次数不能超过 \(y_i\) 。

无法行动（都是 \(0\) 或移动后必定违反限制）的人输，问结果。

注意到值域按照 \(lim_{x_i} = 0\) 分成了若干段（补一个 \(\lim_{-1}=0\) ），对于每段考虑：

从小到大扫描每一个限制，若果存在一个 \(x_i\) 没有限制，那么比他大的都可以变成他；否则按照限制容纳尽可能多的数。

所以操作次数是固定的，模拟即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 100007

int a[N];

#define fr first
#define sc second
#define mp make_pair
#define pb push_back

vector<pii> lim, tmplim;

vector<int> tmp;

inline void work() {
	lim.clear();
	int n = rd(), k = rd();
	for (int i = 1; i <= n; ++i) a[i] = rd();
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= k; ++i) {
		int x = rd(), y = rd();
		lim.push_back(mp(x, y));
	} 
	lim.push_back(mp(1000000001, 0));
	sort(lim.begin(), lim.end());
	int ptr = 1, den = -1, mx = 0;
	ll ans = 0;
	auto calc = [&](){
		int id = 0;
		ll sum = 0, cnt = tmp.size();
		for (auto x : tmp) sum += x;
		ll fin = 0;
		for (int i = den + 1, limid = tmplim.size(); i <= mx; ++i, ++id) {
			if (id >= limid) {fin = i; break;}
			if (tmplim[id].fr > i) {fin = i; break;}
			ll t = min(cnt, (ll)tmplim[id].sc);
			cnt -= t; sum -= t * i;	
			if (!cnt) break;
		}
		sum -= cnt * fin;
		ans += sum;
		tmp.clear();
		tmplim.clear();
	};
	for (auto [x, y] : lim) {
		while (ptr <= n && a[ptr] < x) tmp.pb(a[ptr++]);
		if (y == 0) {mx = x - 1; calc(); den = x;}
		else tmplim.push_back(mp(x, y));
	}
	tmplim.clear();
	tmp.clear();
	puts((ans & 1) ? "Pico" : "FuuFuu");
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

K. I Wanna Maker

数据结构 + 数数。柴老师和胖胖做的。

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
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxq=maxn<<1;

int te,n,tp[maxn+5],L[maxn+5],R[maxn+5];
int lx,ly,rx,ry;
LL ans;
struct DATA {int tp,x,y;};
int Q;DATA q[maxq+5];
multiset<int> S;

inline bool cmp(const DATA &a,const DATA &b) {return a.x<b.x;}
int main(){
	for (scanf("%d",&te);te;te--){
		scanf("%d",&n);
		bool Z=false;
		for (int i=1;i<=n;i++){
			LL k,x;
			scanf("%d%lld%lld",&tp[i],&k,&x);
			if (2*x-k*(k-1)<=0){
				if (tp[i]==1) Z=true;
				else L[i]=1,R[i]=0;
			} else {
				L[i]=(2*x-k*(k-1))/(2*k);
				R[i]=(2*x+k*(k-1)+2*k-1)/(2*k);
			}
		}
		if (Z) goto zero;
		ly=2e9;rx=0;
		for (int i=1;i<=n;i++)
			if (tp[i]==1) ly=min(ly,L[i]),rx=max(rx,R[i]);
		if (ly>rx) goto infty;
		lx=1;ry=2e9;
		for (int i=1;i<=n;i++)
			if (tp[i]==2 && L[i]<=R[i]){
				if (ly<=L[i] && R[i]<=rx) goto zero;
				if (L[i]<ly && R[i]<=rx) lx=max(lx,L[i]+1);
				if (ly<=L[i] && R[i]>rx) ry=min(ry,R[i]-1);
			}
		if (lx>ly || rx>ry) goto zero;
		if (ry==2e9) goto infty;
		Q=0;
		for (int i=1;i<=n;i++)
			if (tp[i]==2 && L[i]<=R[i])
				if (lx<=L[i] && L[i]<ly && rx<R[i] && R[i]<=ry)
					q[++Q]={1,lx,R[i]},q[++Q]={-1,L[i]+1,R[i]};
		ans=(LL)(ly-lx+1)*(ry-rx+1);
		sort(q+1,q+1+Q,cmp);
		S.clear();
		for (int i=1,j=2;i<=Q;i=j){
			for (j=i;j<=Q && q[i].x==q[j].x;j++){
				if (q[j].tp==1) S.insert(q[j].y);
				else S.erase(S.lower_bound(q[j].y));
			}
			if (!S.empty()){
				LL lenr=ry-(*S.begin())+1;
				LL lenl=(j<=Q?q[j].x:ly+1)-q[i].x;
				ans-=lenl*lenr;
			}
		}
		printf("%lld\n",ans);continue;
		zero:puts("0");continue;
		infty:puts("-1");continue;
	}
	return 0;
}