Cod sursa(job #2076627)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 26 noiembrie 2017 21:19:10
Problema Reconst Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("reconst.in");
ofstream cout("reconst.out");
const int nm=2000;
struct fint
{
    int st,dr,val;
};
bool cmp(fint a,fint b)
{
    if(a.st==b.st)
        return a.dr<b.dr;
    return a.st<b.st;
}
fint v[nm+5];
int sol[nm+5],n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>v[i].st>>v[i].dr>>v[i].val;
    while(1)
    {
        sort(v+1,v+m+1,cmp);
        bool ok=1;
        for(int i=1;i<m;i++)
            if(v[i].st==v[i+1].st)
            {
                ok=0;
                if(v[i].dr==v[i+1].dr)
                {
                    v[i+1].dr=v[i+1].st=1e9;
                    sort(v+i+1,v+m+1,cmp);
                    m--;
                    break;
                }
                int stt=v[i].st,drr=v[i].dr,vall=v[i].val;
                v[i].st=v[i].dr+1;
                v[i].dr=v[i+1].dr;
                v[i].val=v[i+1].val-v[i].val;
                v[i+1].st=stt;
                v[i+1].dr=drr;
                v[i+1].val=vall;
            }
        if(ok)
            break;
    }
    int poz=m;
    for(int i=n;i>=1;i--)
        if(i==v[poz].st)
        {
            int s=0;
            for(int j=i+1;j<=v[poz].dr;j++)
                s+=sol[j];
            sol[i]=v[poz].val-s;
            poz--;
        }
    for(int i=1;i<=n;i++)
        cout<<sol[i]<<" ";
    cin.close();
    cout.close();
    return 0;
}