首页 > 代码库 > CodeForces 731D （差分+线段扫描）

CodeForces 731D （差分+线段扫描）

2024-08-17 19:32:06   222人阅读

Description

Archeologists have found a secret pass in the dungeon of one of the pyramids of Cycleland. To enter the treasury they have to open an unusual lock on the door. The lock consists of n words, each consisting of some hieroglyphs. The wall near the lock has a round switch. Each rotation of this switch changes the hieroglyphs according to some rules. The instruction nearby says that the door will open only if words written on the lock would be sorted in lexicographical order (the definition of lexicographical comparison in given in notes section).

The rule that changes hieroglyphs is the following. One clockwise rotation of the round switch replaces each hieroglyph with the next hieroglyph in alphabet, i.e. hieroglyph x (1?≤?x?≤?c?-?1) is replaced with hieroglyph (x?+?1), and hieroglyph c is replaced with hieroglyph 1.

Help archeologist determine, how many clockwise rotations they should perform in order to open the door, or determine that this is impossible, i.e. no cyclic shift of the alphabet will make the sequence of words sorted lexicographically.

Input

The first line of the input contains two integers n and c (2?≤?n?≤?500?000, 1?≤?c?≤?106) — the number of words, written on the lock, and the number of different hieroglyphs.

Each of the following n lines contains the description of one word. The i-th of these lines starts with integer li (1?≤?li?≤?500?000), that denotes the length of the i-th word, followed by li integers wi,?1, wi,?2, ..., wi,?li (1?≤?wi,?j?≤?c) — the indices of hieroglyphs that make up the i-th word. Hieroglyph with index 1 is the smallest in the alphabet and with index c — the biggest.

It‘s guaranteed, that the total length of all words doesn‘t exceed 106.

Output

If it is possible to open the door by rotating the round switch, print integer x (0?≤?x?≤?c?-?1) that defines the required number of clockwise rotations. If there are several valid x, print any of them.

If it is impossible to open the door by this method, print ?-?1.

Sample Input

Input
4 3
2 3 2
1 1
3 2 3 1
4 2 3 1 2
Output
1
Input
2 5
2 4 2
2 4 2
Output
0
Input
4 4
1 2
1 3
1 4
1 2
Output
-1

给你几个单词，你有一种操作，将所有单词的所有字母+1，当然字母最大号为c，c再加上1就变成1了（就1~c轮着转）。问你最少操作几次使得所有的单词满足字典序？如果根本不能满足输出-1。

1.首先介绍下什么是差分法。比如给你一个长度为n的数组cnt，一开始全是0。现在如果让你从下标2~4的位置都+1,怎么做？cnt[2]++,cnt[5]--

数组变成了0 0 1 0 0 -1 0....，我们再进行for（int i=0;i<n;++i）cnt[i]+=cnt[i-1];　　现在变成了0 0 1 1 1 0 0...是不是2~4都+1了？

总结一下，差分的想法就是在区间a~b中+1，等价于cnt[a]++,cnt[b+1]--,然后再处理一边前缀和就行了。

2.什么是线段扫描法？给你n个区间，问你有没有一个公共的区间是这所有n个区间的公共子区间。

首先把这几个区级排好，然后找一条竖着的直线，从左向右平移，然后看有没有一瞬间这个直线与所有区间都相交，及有n个交点。

PS：CF的题目质量真高啊！感觉受益匪浅，这个题是我队友教我的，感谢他。我也要努力超过他！

代码如下：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 vector <int> words[500010];
 5 int cnt[1000010],n,c;//cnt表示转几次是否满足要求
 6 void calc (int a,int b)
 7 {
 8     int idx=0;//idx表示失配位置
 9     while (idx<words[a].size()&&idx<words[b].size())
10     {
11         if (words[a][idx]!=words[b][idx])
12             break;
13         idx++;
14     }
15     if (idx<words[a].size()&&idx<words[b].size())//失配的位置在a,b的中部
16     {
17         if (words[a][idx]<words[b][idx])//在失配位置是b的大于a的
18         {
19             cnt[0]++;
20             cnt[c-words[b][idx]+1]--;
21             cnt[c+1-words[a][idx]]++;
22             cnt[c]--;
23         }
24         else
25         {
26             cnt[c+1-words[a][idx]]++;
27             cnt[c-words[b][idx]+1]--;
28         }
29     }
30     else if (idx==words[a].size()&&idx!=words[b].size())//a比b短
31     {
32         cnt[0]++;                                   //a 123
33         cnt[c]--;                                   //b 123456
34     }
35     else if (idx!=words[a].size()&&idx==words[b].size())//a比b长
36                                                     //a 12345
37                                                     //b 123
38     ;
39     else //a和b完全一样
40     {
41         cnt[0]++;
42         cnt[c]--;
43     }
44 }
45 int main()
46 {
47     //freopen("de.txt","r",stdin);
48     while (~scanf("%d%d",&n,&c))
49     {
50         memset(cnt,0,sizeof cnt);
51         for (int i=0;i<500010;++i)
52         words[i].clear();
53         for (int i=0;i<n;++i)
54         {
55             int len,w;
56             scanf("%d",&len);
57             while (len--)
58             {
59                 scanf("%d",&w);
60                 words[i].push_back(w);
61             }
62         }
63         for (int i=0;i<n-1;++i)
64         calc(i,i+1);
65         bool ok=false;
66         int sum=0;
67         for (int i=0;i<c;++i)
68         {
69             sum+=cnt[i];
70             if (sum==n-1)
71             {
72                 ok=true;
73                 printf("%d\n",i);
74                 break;
75             }
76         }
77         if (!ok)
78         printf("-1\n");
79     }
80     return 0;
81 }

 

CodeForces 731D （差分+线段扫描）


联系
我们