302496: CF482B. Interesting Array

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Interesting Array

题意翻译

构建一个序列a,满足m条限制. 限制形如<l,r,q>: a[l]&a[l+1]&...&a[r-1]&a[r]=q;(此处'&'为位运算的and操作). $1\le n,m\le 10^5,0\le q_i\le 2^{30}$ 由 @Styx 提供翻译

题目描述

We'll call an array of $ n $ non-negative integers $ a\[1\],a\[2\],...,a\[n\] $ interesting, if it meets $ m $ constraints. The $ i $ -th of the $ m $ constraints consists of three integers $ l_{i} $ , $ r_{i} $ , $ q_{i} $ ( $ 1<=l_{i}<=r_{i}<=n $ ) meaning that value ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF482B/c5cfeb39e6b942f975aeab6674c1941b58030e74.png) should be equal to $ q_{i} $ . Your task is to find any interesting array of $ n $ elements or state that such array doesn't exist. Expression $ x&y $ means the bitwise AND of numbers $ x $ and $ y $ . In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".

输入输出格式

输入格式


We'll call an array of $ n $ non-negative integers $ a\[1\],a\[2\],...,a\[n\] $ interesting, if it meets $ m $ constraints. The $ i $ -th of the $ m $ constraints consists of three integers $ l_{i} $ , $ r_{i} $ , $ q_{i} $ ( $ 1<=l_{i}<=r_{i}<=n $ ) meaning that value ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF482B/c5cfeb39e6b942f975aeab6674c1941b58030e74.png) should be equal to $ q_{i} $ . Your task is to find any interesting array of $ n $ elements or state that such array doesn't exist. Expression $ x&y $ means the bitwise AND of numbers $ x $ and $ y $ . In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".

输出格式


We'll call an array of $ n $ non-negative integers $ a\[1\],a\[2\],...,a\[n\] $ interesting, if it meets $ m $ constraints. The $ i $ -th of the $ m $ constraints consists of three integers $ l_{i} $ , $ r_{i} $ , $ q_{i} $ ( $ 1<=l_{i}<=r_{i}<=n $ ) meaning that value ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF482B/c5cfeb39e6b942f975aeab6674c1941b58030e74.png) should be equal to $ q_{i} $ . Your task is to find any interesting array of $ n $ elements or state that such array doesn't exist. Expression $ x&y $ means the bitwise AND of numbers $ x $ and $ y $ . In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".

输入输出样例

输入样例 #1

3 1
1 3 3

输出样例 #1

YES
3 3 3

输入样例 #2

3 2
1 3 3
1 3 2

输出样例 #2

NO

Input

题意翻译

构建一个序列a,满足m条限制. 限制形如<l,r,q>: a[l]&a[l+1]&...&a[r-1]&a[r]=q;(此处'&'为位运算的and操作). $1\le n,m\le 10^5,0\le q_i\le 2^{30}$ 由 @Styx 提供翻译

加入题单

算法标签: