写起来很麻烦的一道题。不过思路还算简单。

首先不考虑套娃的情况。len的长度内有a个0和b=len-a个1，最多会产生a*b个01子序列。在范围内可以使用如下的策略进行填充。

（对应代码中的fill函数）从左到右，记录当前剩余未填充的1数量cnt1，还需产生的01序列数量k。

如果k>=cnt1，那么填充一个0，因为后面无论如何分配都一定有cnt1个1，总会产生cnt1个01子序列。

否则填充一个1，使得cnt1--。

容易知道这样肯定是能填充满的。

接下来是套娃的情况。将区域分为左，中，右三个部分，其中中间是之前已经填充好的，左边和右边需要现在填充。

这里没必要计算太复杂的约束，可以以O(n)的效率枚举，一共有x个0和y个1需要分配到左右两边，那么我可以假设左边分配cnt0L个0，从而cnt0R=x-cnt0L，对于1的数量也同样计算。

在上述分配条件下，一定会产生的01子序列如下：

  • 原本中间部分就有的01子序列数量
  • 左边部分的每个0和中间部分的每个1一定产生01子序列
  • 中间部分的每个0和右边部分的每个1一定产生01子序列
  • 左边部分的每个0和右边部分的每个1一定产生

有可能产生的01子序列的情况就是左边自己和右边自己。 如果两边各自都把1放到前面0放到后面，就不会产生额外的。其实就转化成了一开始说的不带套娃的子问题。

直接枚举每种分配方案，找到一种合适的就继续跑下一层，找不到合适的直接-1。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;

int n,m;
int l[N],r[N],a[N],b[N],c[N];
pair<pair<int,int>,int> d[N];
int ans[N];


void fill(int l,int r,int cnt0,int k)
{
    int cnt1 = r-l+1-cnt0;
    for(int i=l;i<=r;i++)
    {
        if(k>=cnt1)k-=cnt1;
        else ans[i]=1,cnt1--;
    }
}


int main() {
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i]>>a[i]>>b[i]>>c[i];
        d[i].first.first = -l[i];
        d[i].first.second = r[i];
        d[i].second = i;
    }
    sort(d+1,d+m+1);
    for(int i=1;i<=m;i++)
    {
        int p = d[i].second;
        int pre = d[i-1].second;
        int prel = l[pre],prer=r[pre];
        int lenl = l[pre]-l[p];
        int lenr = r[p]-r[pre];
        int basea=a[pre],baseb=b[pre],basec=c[pre];
        if(i==1)lenl=0,lenr=r[p]-l[p]+1,basea=baseb=basec=0;
        int cnt0 = a[p] - basea;
        bool flag = false;
        for(int x=0;x<=min(cnt0,lenl);x++)
        {
            int cnt0l=x,cnt0r=cnt0-x;
            int cnt1l=lenl-cnt0l;
            int cnt1r=lenr-cnt0r;
            int basek = basec+cnt0l*baseb+cnt1r*basea+cnt0l*cnt1r;
            int addonk=cnt0l*cnt1l+cnt0r*cnt1r;
            if(cnt1l<0||cnt1r<0)continue;
            if(c[p]>basek+addonk||c[p]<basek)continue;
            flag = true;
            int addon = c[p]-basek;
            if(addon<=cnt0l*cnt1l)
            {
                fill(l[p],l[p]+lenl-1,cnt0l,addon);
                fill(r[p]-lenr+1,r[p],cnt0r,0);
            }
            else 
            {
                fill(l[p],l[p]+lenl-1,cnt0l,cnt0l*cnt1l);
                fill(r[p]-lenr+1,r[p],cnt0r,addon-cnt0l*cnt1l);
            }
            break;
        }
        if(!flag)
        {
            cout<<-1;
            return 0;
        }
    }
    for(int i=1;i<=n;i++)cout<<ans[i];
}
// 64 位输出请用 printf("%lld")