Submission #90938

#	Time	Username	Problem	Language	Result	Execution time	Memory
90938		Aydarov03	Trading (IZhO13_trading)	C++14	100 / 100	270 ms	16040 KiB

trading

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int tree[300005 * 4];
int n , m , l , r , x;


void push( int tl , int tr , int v)
{
    if( tl == tr )return;
    tree[v + v] = max( tree[v + v] , tree[v] );
    tree[v+v+1] = max( tree[v+v+1] , tree[v] + ( (tr-tl+2)/2 )  );

//    cout << tree[v+v] << " - " << tree[v+v+1] << endl;
}

void upd( int l , int r , int val , int v = 1 , int tl = 1 , int tr = n )
{
    if( tree[v] )
    push( tl , tr , v );

    if( tl > r || tr < l )return;
    if( l <= tl && tr <= r )
    {
        tree[v] = max( tree[v] , val + ( tl - l ) );
//        cout << '(' << v << ')' << tl << " " << tr << " -> " << tree[v] << endl;
        push( tl , tr , v );
        return;
    }
    int mid = (tl + tr) / 2;
    upd( l , r , val , v + v , tl , mid );
    upd( l , r , val , v+v+1 , mid+1 , tr );
}


void get( int pos , int v = 1 , int tl = 1 , int tr = n )
{
//    cout << tl << " " << tr << endl;
    if( tree[v] )push( tl , tr , v );

    if( tl == tr )
    {
        cout << tree[v] << " ";
        return;
    }

    int mid = (tl + tr) / 2;
    if( pos <= mid )
        get( pos , v + v , tl , mid);
    else
        get( pos , v+v+1 , mid+1 , tr);
}



main()
{
    IOS;
    cin >> n >> m;


    for(int i = 1; i <= m; i++)
    {
        cin >> l >> r >> x;
        upd( l , r , x );
    }

    for(int i = 1; i <= n; i++)
        get( i );


//    for(int i = 1; i <= n * 4; i++)
//        if( tree[i] )cout << i << " " << tree[i] << endl;

}
// 5 2 1 3 1 3 5 2
//2 1
//3 3
//4 1
//5 3
//6 3
//7 7
//8 1
//9 2

Compilation message (stderr)

trading.cpp:56:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

• Subtask 1: 100 / 100