QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#77307#2559. Endless RoadSortingWA 5ms46888kbC++8.1kb2023-02-14 03:01:292023-02-14 03:01:33

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-14 03:01:33]
  • 评测
  • 测评结果：WA
  • 用时：5ms
  • 内存：46888kb
查看
  • [2023-02-14 03:01:29]
  • 提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ; 
typedef vector<int> vi;
typedef unsigned int uint ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 5e5 + 7 ;
const ll inf = 1e18 + 7 ;

int n ;
struct range {
    int l , r ;
    int id , rem ;
};
range a[ MAXN ] ;
map < int , int > nwvals ;
int rev_vals[ MAXN ] ;
int mxval ;
int lens[ MAXN ] ;

class sum_tree {
public :
    ll tr[ 4 * MAXN ] ;
    void init ( int w , int l , int r ) {
        if ( l == r ) {
            tr[ w ] = lens[ l ] ;
            return ;
        }
        int mid = ( l + r ) / 2 ;
        init ( 2 * w , l , mid ) ;
        init ( 2 * w + 1 , mid + 1 , r ) ;
        tr[ w ] = tr[ 2 * w ] + tr[ 2 * w + 1 ] ;
    }
    void update ( int w , int l , int r , int pos , ll add ) {
        if ( l == r ) {
            tr[ w ] += add ;
            return ;
        }
        int mid = ( l + r ) / 2 ;
        if ( pos <= mid ) { update ( 2 * w , l , mid , pos , add ) ; }
        else { update ( 2 * w + 1 , mid + 1 , r , pos , add ) ; }
        tr[ w ] = tr[ 2 * w ] + tr[ 2 * w + 1 ] ;
    }
    ll query ( int w , int l , int r , int st , int en ) {
        if ( l > r || st > en ) { return 0 ; }
        if ( r < st || en < l ) { return 0 ; }
        if ( st <= l && r <= en ) { return tr[ w ] ; }
        int mid = ( l + r ) / 2 ;
        return query ( 2 * w , l , mid , st , en ) + query ( 2 * w + 1 , mid + 1 , r , st , en ) ;
    }
};
sum_tree w_sum ;

class min_tree {
public :
    pii tr[ 4 * MAXN ] ;
    pii unite ( pii p1 , pii p2 ) {
        if ( p2.fi <= p1.fi ) { return p2 ; }
        return p1 ;
    }
    void init ( int w , int l , int r ) {
        if ( l == r ) {
            tr[ w ] = { a[ l ].r , l } ;
            return ;
        }
        int mid = ( l + r ) / 2 ;
        init ( 2 * w , l , mid ) ;
        init ( 2 * w + 1 , mid + 1 , r ) ;
        tr[ w ] = unite ( tr[ 2 * w ] , tr[ 2 * w + 1 ] ) ;
    }
    void update ( int w , int l , int r , int pos ) {
        if ( l == r ) {
            tr[ w ] = { MAXN , l } ;
            return ;
        }
        int mid = ( l + r ) / 2 ;
        if ( pos <= mid ) { update ( 2 * w , l , mid , pos ) ; }
        else { update ( 2 * w + 1 , mid + 1 , r , pos ) ; }
        tr[ w ] = unite ( tr[ 2 * w ] , tr[ 2 * w + 1 ] ) ;
    }
    pii query ( int w , int l , int r , int st , int en ) {
        if ( l > r || st > en ) { return { MAXN , MAXN } ; }
        if ( r < st || en < l ) { return { MAXN , MAXN } ; }
        if ( st <= l && r <= en ) { return tr[ w ] ; }
        int mid = ( l + r ) / 2 ;
        return unite ( query ( 2 * w , l , mid , st , en ) , query ( 2 * w + 1 , mid + 1 , r , st , en ) ) ;
    }
};
min_tree current_min ;


class rem_sum_tree {
public :
    pair < ll , int > tr[ 4 * MAXN ] ;
    ll lazy[ 4 * MAXN ] ;
    void push_lazy ( int w , int l , int r ) {
        tr[ w ].fi += lazy[ w ] ;
        if ( l != r ) {
            lazy[ 2 * w ] += lazy[ w ] ;
            lazy[ 2 * w + 1 ] += lazy[ w ] ;
        }
        lazy[ w ] = 0 ;
    }
    pair < ll , int > unite ( pair < ll , int > p1 , pair < ll , int > p2 ) {
        if ( p1.fi < p2.fi ) { return p1 ; }
        else if ( p2.fi < p1.fi ) { return p2 ; }
        else {
            if ( a[ p1.se ].id < a[ p2.se ].id ) { return p1 ; }
            return p2 ;
        }
    }
    void init ( int w , int l , int r ) {
        lazy[ w ] = 0 ;
        if ( l == r ) { 
            tr[ w ] = { inf , l } ;
            return ;
        }
        int mid = ( l + r ) / 2 ;
        init ( 2 * w , l , mid ) ;
        init ( 2 * w + 1 , mid + 1 , r ) ;
        tr[ w ] = unite ( tr[ 2 * w ] , tr[ 2 * w + 1 ] ) ;
    }
    void update ( int w , int l , int r , int st , int en , ll add ) {
        push_lazy ( w , l , r ) ;
        if ( l > r || st > en ) { return ; }
        if ( r < st || en < l ) { return ; }
        if ( st <= l && r <= en ) {
            lazy[ w ] += add ;
            push_lazy ( w , l , r ) ;
            return ;
        }
        int mid = ( l + r ) / 2 ;
        update ( 2 * w , l , mid , st , en , add ) ;
        update ( 2 * w + 1 , mid + 1 , r , st , en , add ) ;
        tr[ w ] = unite ( tr[ 2 * w ] , tr[ 2 * w + 1 ] ) ;
    }
    int query ( ) { return tr[ 1 ].se ; }
};

rem_sum_tree rem_lens ;

set < pii > cands_left , cands_right ;
set < int > alive ;

void solve ( ) {
    cin >> n ;
    vector < int > all_vals ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].l >> a[ i ].r ;
        a[ i ].rem = a[ i ].r - a[ i ].l ;
        a[ i ].id = i ;
        all_vals.push_back ( a[ i ].l ) ;
        all_vals.push_back ( a[ i ].r ) ;
    }
    sort ( all_vals.begin ( ) , all_vals.end ( ) ) ;
    nwvals[ all_vals[ 0 ] ] = 1 ;
    rev_vals[ 1 ] = all_vals[ 0 ] ;
    mxval = 1 ;
    for ( int i = 1 ; i < 2 * n ; ++ i ) {
        if ( all_vals[ i ] == all_vals[ i - 1 ] ) { continue ; }
        nwvals[ all_vals[ i ] ] = ++ mxval ;
        rev_vals[ mxval ] = all_vals[ i ] ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        a[ i ].l = nwvals[ a[ i ].l ] ;
        a[ i ].r = nwvals[ a[ i ].r ] ;
    }
    auto cmp = [ & ] ( range p1 , range p2 ) {
        if ( p1.l != p2.l ) { return ( p1.l < p2.l ) ; }
        return ( p1.r > p2.r ) ;
    };
    sort ( a + 1 , a + n + 1 , cmp ) ;
    for ( int i = 1 ; i < mxval ; ++ i ) {
        lens[ i ] = rev_vals[ i + 1 ] - rev_vals[ i ] ;
        alive.insert ( i ) ;
    }
    w_sum.init ( 1 , 1 , mxval - 1 ) ;
    current_min.init ( 1 , 1 , n ) ;
    rem_lens.init ( 1 , 1 , n ) ;
    int lst = 0 ;
    while ( 1 ) {
        auto [ val , id ] = current_min.query ( 1 , 1 , n , lst + 1 , n ) ;
        if ( val == MAXN ) { break ; }
        cands_left.insert ( { a[ id ].l , id } ) ;
        cands_right.insert ( { a[ id ].r , id } ) ;
        rem_lens.update ( 1 , 1 , n , id , id , -inf + w_sum.query ( 1 , 1 , mxval - 1 , a[ id ].l , a[ id ].r - 1 ) ) ;
        current_min.update ( 1 , 1 , n , id ) ;
        lst = id ;
    }
    for ( int ctr = 0 ; ctr < n ; ++ ctr ) {
        int wh = rem_lens.query ( ) ;
        cout << a[ wh ].id << " " ;
        cands_left.erase ( { a[ wh ].l , wh } ) ;
        cands_right.erase ( { a[ wh ].r , wh } ) ;
        rem_lens.update ( 1 , 1 , n , wh , wh , inf ) ;
        while ( 1 ) {
            auto it = alive.lower_bound ( a[ wh ].l ) ;
            if ( it == alive.end ( ) || *it >= a[ wh ].r ) { break ; }
            int pos = *it ;
            alive.erase ( pos ) ;
            w_sum.update ( 1 , 1 , mxval - 1 ,  pos , -lens[ pos ] ) ;
            auto r_end = cands_left.upper_bound ( make_pair ( pos , MAXN ) ) ;
            auto l_end = cands_right.lower_bound ( make_pair ( pos , -MAXN ) ) ;
            if ( l_end == cands_right.end ( ) || r_end == cands_left.begin ( ) ) { continue ; }
            -- r_end ;
            if ( l_end->se > r_end->se ) { continue ; }
            rem_lens.update ( 1 , 1 , n , l_end->se , r_end->se , -lens[ pos ] ) ;
        }
        int lst = 0 ;
        auto it = cands_left.lower_bound ( make_pair ( a[ wh ].l , wh ) ) ;
        int en = n + 1 ;
        int lim = MAXN ;
        if ( it != cands_left.end ( ) ) {
            lim = it->fi ;
            en = it->se ;
        }
        if ( it != cands_left.begin ( ) ) {
            -- it ;
            lst = it->se ;
        }
        while ( 1 ) {
            auto [ val , id ] = current_min.query ( 1 , 1 , n , lst + 1 , en - 1 ) ;
            if ( val == MAXN || val > lim ) { break ; }
            cands_left.insert ( { a[ id ].l , id } ) ;
            cands_right.insert ( { a[ id ].r , id } ) ;
            rem_lens.update ( 1 , 1 , n , id , id , -inf + w_sum.query ( 1 , 1 , mxval - 1 , a[ id ].l , a[ id ].r - 1 ) ) ;
            current_min.update ( 1 , 1 , n , id ) ;
            lst = id ;
        }
    }
    cout << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}
Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 44688kb

input:

6
1 2
2 3
3 4
4 5
1 3
3 5

output:

1 2 5 3 4 6

result:

ok 6 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 46888kb

input:

4
3 7
10 14
1 6
6 11

output:

1 3 2 4

result:

ok 4 tokens

Test #3:

score: 0
Accepted
time: 1ms
memory: 45024kb

input:

100
50 51
49 51
49 52
48 52
48 53
47 53
47 54
46 54
46 55
45 55
45 56
44 56
44 57
43 57
43 58
42 58
42 59
41 59
41 60
40 60
40 61
39 61
39 62
38 62
38 63
37 63
37 64
36 64
36 65
35 65
35 66
34 66
34 67
33 67
33 68
32 68
32 69
31 69
31 70
30 70
30 71
29 71
29 72
28 72
28 73
27 73
27 74
26 74
26 75
25...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

result:

ok 100 tokens

Test #4:

score: -100
Wrong Answer
time: 5ms
memory: 46328kb

input:

100
41 42
99 100
47 48
50 51
56 57
61 62
27 28
85 86
44 45
3 4
26 27
20 21
92 93
33 34
86 87
69 70
84 85
62 63
81 82
2 3
13 14
32 33
82 83
70 71
46 47
45 46
19 20
83 84
57 59
63 65
59 61
82 84
45 47
48 50
70 72
42 44
84 86
26 28
61 63
2 4
17 19
65 67
54 56
67 69
96 99
42 45
47 50
34 37
14 17
51 54
7...

output:

1 2 3 25 26 9 33 4 5 6 7 11 38 8 17 28 23 19 32 37 10 20 40 12 27 13 14 22 15 16 18 39 21 24 31 29 57 73 34 47 71 35 36 46 41 53 43 54 44 42 30 52 58 77 49 64 80 50 60 79 91 45 55 63 65 83 48 62 51 66 89 59 67 86 61 72 82 90 96 56 68 75 81 93 69 74 84 92 70 87 88 94 97 99 76 78 85 95 98 100

result:

wrong answer 4th words differ - expected: '4', found: '25'
English 繁體中文 简体中文

Server Time: 2025-01-20 21:15:41 | OpenSource Project