Cod sursa(job #1972021)

Utilizator refugiatBoni Daniel Stefan refugiat Data 21 aprilie 2017 15:23:08
Problema Reconst Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream si("reconst.in");
ofstream so("reconst.out");
struct inter
{
    int st,dr,s;
};
bool comp(inter a,inter b)
{
    if(a.st<b.st)
        return true;
    if(a.st>b.st)
        return false;
    return a.dr<b.dr;
}
int v[2005];
inter x[2005];
int sum[2005];
int main()
{
    int n,m;
    si>>n>>m;
    for(int i=1;i<=m;++i)
    {
        si>>x[i].st>>x[i].dr>>x[i].s;
    }
    sort(x+1,x+1+m,comp);
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<i;++j)
        {
            if(x[i].st==x[j].st)
            {
                x[i].st=x[j].dr+1;
                x[i].s-=x[j].s;
            }
        }
        //cout<<x[i].st<<' '<<x[i].dr<<' '<<x[i].s<<'\n';
    }
    sort(x+1,x+1+m,comp);
    int poz=m;
    for(int i=n;i;--i)
    {
        while(poz&&(x[poz].st>x[poz].dr||x[poz].st>i))
            --poz;
        if(poz&&x[poz].st==i)
        {
            v[i]=x[poz].s-sum[i+1]+sum[x[poz].dr+1];
        }
        else
            v[i]=0;
        sum[i]=sum[i+1]+v[i];
    }
    for(int i=1;i<=n;++i)
        so<<v[i]<<' ';
    return 0;
}