oj.uz

Submission #90938

# Submission time Handle Problem Language Result Execution time Memory
90938 2018-12-25T09:05:56 Z Aydarov03 Trading (IZhO13_trading) C++14
100 / 100
 270 ms 16040 KB 
#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

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 4 ms 612 KB Output is correct
7 Correct 140 ms 5700 KB Output is correct
8 Correct 148 ms 9592 KB Output is correct
9 Correct 153 ms 12496 KB Output is correct
10 Correct 162 ms 12496 KB Output is correct
11 Correct 170 ms 14112 KB Output is correct
12 Correct 191 ms 14112 KB Output is correct
13 Correct 193 ms 14656 KB Output is correct
14 Correct 196 ms 14656 KB Output is correct
15 Correct 225 ms 14656 KB Output is correct
16 Correct 241 ms 14656 KB Output is correct
17 Correct 224 ms 15480 KB Output is correct
18 Correct 244 ms 16020 KB Output is correct
19 Correct 237 ms 16020 KB Output is correct
20 Correct 270 ms 16040 KB Output is correct