oj.uz

답안 #168542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168542 2019-12-13T15:36:51 Z muhammad_hokimiyon 거래 (IZhO13_trading) C++14
0 / 100
 226 ms 15608 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] == -1 )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
0 / 100.0

# 결과 실행 시간 메모리 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 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 152 ms 10664 KB Output is correct
8 Correct 170 ms 12028 KB Output is correct
9 Correct 178 ms 12288 KB Output is correct
10 Correct 188 ms 13048 KB Output is correct
11 Correct 201 ms 14128 KB Output is correct
12 Correct 217 ms 14856 KB Output is correct
13 Incorrect 226 ms 15608 KB Output isn't correct
14 Halted 0 ms 0 KB -