【39.66%】【codeforces 740C】Alyona and mex
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Alyona’s mother wants to present an array of n non-negative integers to Alyona. The array should be special.
Alyona is a capricious girl so after she gets the array, she inspects m of its subarrays. Subarray is a set of some subsequent elements of the array. The i-th subarray is described with two integers li and ri, and its elements are a[li], a[li + 1], …, a[ri].
Alyona is going to find mex for each of the chosen subarrays. Among these m mexes the girl is going to find the smallest. She wants this minimum mex to be as large as possible.
You are to find an array a of n elements so that the minimum mex among those chosen by Alyona subarrays is as large as possible.
The mex of a set S is a minimum possible non-negative integer that is not in S.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 105).
The next m lines contain information about the subarrays chosen by Alyona. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), that describe the subarray a[li], a[li + 1], …, a[ri].
Output
In the first line print single integer — the maximum possible minimum mex.
In the second line print n integers — the array a. All the elements in a should be between 0 and 109.
It is guaranteed that there is an optimal answer in which all the elements in a are between 0 and 109.
If there are multiple solutions, print any of them.
Examples
input
5 3
1 3
2 5
4 5
output
2
1 0 2 1 0
input
4 2
1 4
2 4
output
3
5 2 0 1
Note
The first example: the mex of the subarray (1, 3) is equal to 3, the mex of the subarray (2, 5) is equal to 3, the mex of the subarray (4, 5) is equal to 2 as well, thus the minumal mex among the subarrays chosen by Alyona is equal to 2.
【题目链接】:http://codeforces.com/contest/740/problem/C
【题解】
考虑一下所有区间;最后的答案肯定不大于所有区间里面长度最小的那个;
因为如果答案大于区间长度最小的区间li,ri;
则ri-li+1小于ans;
则li-ri这个区间是怎么样都没办法凑出ans的;
因为区间内数字最大的办法是
0 1 2 …ri-li;然后mex==ri-li+1;
所以答案肯定小于等于min(ri-li+1);
然后就开始“贪心”呗;
就假设答案是ans=min(ri-li+1);
会发现;只要按照如下的方法复制序列;就总能满足题意;
即
0 1 2 3 ..ans-1 0 1 2 ….
即以ans-1为循环节在需要满足的m个区间里面周期性地复制这个序列就可以了
如ans=3
然后m个区间把1..n都覆盖了
则在1..n假设n=7应该满足
0 1 2 0 1 2 0
这样长度为3的区间,里面最大的值都是2,则mex为2+1==3;
而长度为4的区间也是一样。总能满足最大值是2,mex为3;
看起来贪心 成功了;
然后我就交了
用线段树搞出1-n上哪些点被覆盖了;
然后再连续的段上不断复制那个1..ans-1的周期串就好了;
其他没被覆盖的点直接输出0就好;
(另解:不用搞线段树,直接在1..n上管他有没有被覆盖,直接覆盖0..ans-1的周期串。这样也是对的.挺容易想明白的);下面贴的是线段树的代码;另解的代码就更简单了;不贴了;
【完整代码】
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1e5+100;
LL n,m;
bool bo[MAXN] = {0};
int color[MAXN << 2],l[MAXN],r[MAXN],a[MAXN];
void push_down(int rt)
{
if (color[rt] != -1)
{
color[rt << 1] = color[rt << 1 | 1] = color[rt];
color[rt] = -1;
}
}
void updata(int l, int r, int num,int begin, int end, int rt)
{
if (l <= begin && end <= r)
{
color[rt] = num;
return;
}
push_down(rt);
int m = (begin + end) >> 1;
if (l <= m)
updata(l, r, num, begin, m, rt << 1);
if (m < r)
updata(l, r, num, m + 1, end, rt << 1 | 1);
}
bool query(int pos,int begin,int end,int rt)
{
if (begin==end)
{
if (color[rt]==1)
return true;
else
return false;
}
push_down(rt);
int m = (begin+end)>>1;
if (pos <= m)
return query(pos,begin,m,rt<<1);
else
return query(pos,m+1,end,rt<<1|1);
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
memset(color,255,sizeof(color));
cin >> n >> m;
int mi = 21e8;
for (int i = 1;i <= m;i++)
{
int li,ri;
cin >> l[i] >> r[i];
updata(l[i],r[i],1,1,n,1);
mi = min(mi,r[i]-l[i]+1);
}
for (int i = 1;i <= n;i++)
{
if (query(i,1,n,1))
bo[i] = true;
else
bo[i] =false;
}
for (int i = 1;i <= n;i++)
{
if (bo[i] == true)
{
int j = i+1;
while (j<=n && bo[j]==true)
j++;
int now = 0;
for (int k = i;k <= j-1;k++)
{
a[k] = now;
now++;
if (now >mi-1)
now = 0;
}
i = j-1;
}
}
cout << mi << endl;
for (int i = 1;i <= n;i++)
if (i==n)
printf("%d\n",a[i]);
else
printf("%d ",a[i]);
return 0;
}
相关文章
- CRM WebUI and Hybris的Product页面标题实现
- [git] git遇到的问题Please make sure you have the correct access rights and the repository exists.”
- [Tools] Fix Only Committed Files with Prettier and lint-staged
- [Javascript] Format console.log with CSS and String Template Tags
- [Practical Git] Switching between current branch and last checkout branch
- [TypeScript] Installing TypeScript and Running the TypeScript Compiler (tsc)
- [Algorithm] 122. Best Time to Buy and Sell Stock II
- [Angular] FadeIn and FadeOut animation in Angular
- SAP UI5 Repository and MongoDB Repository
- Atitit 锁的不同层级 app锁 vm锁 os锁 硬件锁 目录 1. 在硬件层面,CPU提供了原子操作、关中断、锁内存总线的机制1 1.1. test and set指令1 1.2. 锁内
- Atitit.struts排除url 的设计and 原理 自定义filter 排除特定url
- 【Codeforces Round #482 (Div. 2) C】Kuro and Walking Route
- 【Codeforces Round #442 (Div. 2) C】Slava and tanks
- 【27.91%】【codeforces 734E】Anton and Tree
- 【64.22%】【codefoces round 382A】Ostap and Grasshopper
- 【codeforces 791C】Bear and Different Names
- 【codeforces 761C】Dasha and Password(贪心+枚举做法)
- 【codeforces 754D】Fedor and coupons
- 【codeforces 754B】 Ilya and tic-tac-toe game
- 【codeforces 755C】PolandBall and Forest
- 【codeforces 752F】Santa Clauses and a Soccer Championship
- 【codeforces 548A】Mike and Fax
- 【codeforces 798D】Mike and distribution
- 【Codeforces Round #432 (Div. 1) C】 Arpa and a game with Mojtaba
- 【Codeforces Round #430 (Div. 2) D】Vitya and Strange Lesson
- 【codeforces 743E】Vladik and cards
- PAT 1062 Talent and Virtue[难]