CompetitiveProgramming/codeforces/100959/F.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
#include <bits/stdc++.h>
using namespace std;
const int MAX = int(1e9), LIM = int(1e5);

int n, a[22], c[22];
map <int,int> flag;

int isGood(int m)
{
  for (int i = 0; i < n;)
  {
    int j = i;
    while (j < n && c[j] == c[i])
    {
      if (a[j] / m != a[i] / m)
        return 0;
      j++;
    }
    i = j;
    if (i < n && a[i] / m == a[i - 1] / m)
      return 0;
  }

  return 1;
}

void checkSame(int u, int v)
{
  if (u == v) return;
  for (int i = 0; i <= MAX / LIM; i++)
  {
    int low = u / (i + 1);
    if (low * (i + 1) <= u) low++;
    int high = v / (i + 1);
    if (i) high = min(high, u / i);
    if (low <= high && high > LIM)
    {
      flag[max(low, LIM + 1)]++;
      flag[high + 1]--;
    }
  }
}

void checkDif(int u, int v)
{
  for (int i = 0; i <= MAX / LIM; i++)
  {
    int low = v / (i + 1);
    if (low * (i + 1) <= v) low++;
    int high = i ? u / i : MAX;
    if (low <= high && high > LIM)
    {
      flag[max(low, LIM + 1)]++;
      flag[high + 1]--;
    }
  }
}

int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> a[i] >> c[i];
    a[i]--;
    for (int j = 0; j < i; j++)
      if (c[j] == c[i])
        for (int k = j + 1; k < i; k++)
          if (c[k] != c[i])
          {
            cout << 0 << endl;
            return 0;
          }
  }

  if (c[0] == c[n - 1])
  {
    cout << -1 << endl;
    return 0;
  }

  int ans = 0;
  for (int m = 1; m <= LIM; m++)
    ans += isGood(m);

  flag[LIM + 1] = 0;
  for (int i = 0; i < n;)
  {
    int j = i;
    while (j < n && c[j] == c[i])
      j++;
    checkSame(a[i], a[j - 1]);
    if (j < n)
      checkDif(a[j - 1], a[j]);
    i = j;
  }

  int last = LIM + 1, cur = 0;
  for (auto u : flag)
  {
    if (!cur)
      ans += u.first - last;
    cur += u.second;
    last = u.first;
  }

  cout << ans << endl;
}