oj.uz

Submission #168544

# Submission time Handle Problem Language Result Execution time Memory
168544 2019-12-13T15:39:39 Z muhammad_hokimiyon Trading (IZhO13_trading) C++14
100 / 100
 297 ms 20984 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

#define fi first
#define se second
#define ll long long

using namespace std;

const int N = 4e5 + 7;
const int mod = 1e9 + 7;

int n,q;
int l[N];
int r[N];
int z[N];
int lz[4 * N];
int t[4 * N];

void push( int x )
{
    if( lz[x] == -1e9 )return;
    t[x * 2] = max( t[x * 2] , lz[x] );
    t[x * 2 + 1] = max( t[x * 2 + 1] , lz[x] );
    lz[x * 2] = max( lz[x * 2] , lz[x] );
    lz[x * 2 + 1] = max( lz[x * 2 + 1] , lz[x] );
    lz[x] = -1e9;
}

void upd( int x , int l , int r , int tl , int tr , int val )
{
    if( tl > tr )return;
    if( l == tl && r == tr ){
        t[x] = max( t[x] , val );
        lz[x] = max( lz[x] , val );
        return;
    }
    int m = (l + r) / 2;
    push(x);
    upd( x * 2 , l , m , tl , min(tr , m) , val );
    upd( x * 2 + 1 , m + 1 , r , max(tl , m + 1) , tr , val );
}

int get( int x , int l , int r , int pos )
{
    if( l == r ){
        return t[x];
    }
    int m = (l + r) / 2;
    push(x);
    if( m >= pos )return get( x * 2 , l , m , pos );
    else return get( x * 2 + 1 , m + 1 , r , pos );
}

void solve()
{
    cin >> n >> q;
    for( int i = 1; i <= 4 * n; i++ ){
        t[i] = lz[i] = -1e9;
    }
    for( int i = 1; i <= q; i++ ){
        cin >> l[i] >> r[i] >> z[i];
        z[i] -= l[i];
        upd( 1 , 1 , n , l[i] , r[i] , z[i] );
    }
    for( int i = 1; i <= n; i++ ){
        int ans = get( 1 , 1 , n , i );
        if( ans == -1e9 )ans = -i;
        cout << ans + i << " ";
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int t = 1;//cin >> t;
    while( t-- ){
        solve();
    }
}

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 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 145 ms 7672 KB Output is correct
8 Correct 156 ms 8696 KB Output is correct
9 Correct 165 ms 8956 KB Output is correct
10 Correct 176 ms 9336 KB Output is correct
11 Correct 186 ms 10488 KB Output is correct
12 Correct 201 ms 10732 KB Output is correct
13 Correct 209 ms 11384 KB Output is correct
14 Correct 212 ms 15948 KB Output is correct
15 Correct 240 ms 17272 KB Output is correct
16 Correct 250 ms 17656 KB Output is correct
17 Correct 237 ms 18124 KB Output is correct
18 Correct 265 ms 18680 KB Output is correct
19 Correct 261 ms 18808 KB Output is correct
20 Correct 297 ms 20984 KB Output is correct