oj.uz

Submission #31427

# Submission time Handle Problem Language Result Execution time Memory
31427 2017-08-23T16:05:52 Z chonka Fortune Telling 2 (JOI14_fortune_telling2) C++
100 / 100
 529 ms 54196 KB 
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std ;

#define MAXN 200007

int n , q ;
int a[ MAXN ] ;
int b[ MAXN ] ;

int x[ MAXN ] ;

int lst[ MAXN ] ;

pair < int , int > srt[ MAXN ] ;

vector < pair < int , int > > v ;


class DumbTree {
    public :
    int tr[ 3 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        tr[ where ] = 0 ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void update ( int where , int IL , int IR , int pos ) {
        if ( IL == IR ) {
            tr[ where ] = x[ IL ] ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            update ( 2 * where , IL , mid , pos ) ;
        }
        else {
            update ( 2 * where + 1 , mid + 1 , IR , pos ) ;
        }
        tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
    }
    int find ( int where , int IL , int IR , int sr ) {
        if ( tr[ where ] < sr ) { return 0 ; }
        if ( IL == IR ) { return IL ; }
        int mid = ( IL + IR ) / 2 ;
        if ( tr[ 2 * where + 1 ] >= sr ) {
            return find ( 2 * where + 1 , mid + 1 , IR , sr ) ;
        }
        return find ( 2 * where , IL , mid , sr ) ;
    }
};
DumbTree u ;



class Tree {
    public :
    vector < int > tr[ 3 * MAXN ] ;
    void merge ( int where ) {
        int sz1 = tr[ 2 * where ].size ( ) ;
        int sz2 = tr[ 2 * where + 1 ].size ( ) ;
        int pos1 , pos2 ;
        pos1 = pos2 = 0 ;
        while ( pos1 != sz1 || pos2 != sz2 ) {
            if ( pos2 == sz2 ) {
                tr[ where ].push_back ( tr[ 2 * where ][ pos1 ] ) ;
                pos1 ++ ;
            }
            else if ( pos1 == sz1 ) {
                tr[ where ].push_back ( tr[ 2 * where + 1 ][ pos2 ] ) ;
                pos2 ++ ;
            }
            else {
                if ( tr[ 2 * where ][ pos1 ] < tr[ 2 * where + 1 ][ pos2 ] ) {
                    tr[ where ].push_back ( tr[ 2 * where ][ pos1 ] ) ;
                    pos1 ++ ;
                }
                else {
                    tr[ where ].push_back ( tr[ 2 * where + 1 ][ pos2 ] ) ;
                    pos2 ++ ;
                }
            }
        }
    }
    void init ( int where , int IL , int IR ) {
        if ( IL == IR ) {
            tr[ where ].push_back ( x[ IL ] ) ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
        merge ( where ) ;
    }
    int bin ( int where , int sr ) {
        int l , r , mid ;
        l = 0 ;
        r = tr[ where ].size ( ) - 1 ;
        if ( tr[ where ][ 0 ] >= sr ) { return ( r + 1 ) ; }
        if ( tr[ where ][ r ] < sr ) { return 0 ; }
        while ( ( r - l ) > 3 ) {
            mid = ( l + r ) / 2 ;
            if ( tr[ where ][ mid ] >= sr ) { r = mid ; }
            else { l = mid ; }
        }
        while ( tr[ where ][ l ] < sr ) { l ++ ; }
        return ( tr[ where ].size ( ) - l ) ;
    }
    int query ( int where , int IL , int IR , int pos , int sr ) {
        if ( IL > IR ) { return 0 ; }
        if ( IR < pos ) { return 0 ; }
        if ( pos <= IL ) {
            return bin ( where , sr ) ;
        }
        int mid = ( IL + IR ) / 2 ;
        return ( query ( 2 * where , IL , mid , pos , sr ) + query ( 2 * where + 1 , mid + 1 , IR , pos , sr ) ) ;
    }
};

Tree w ;

void input ( ) {
    scanf ( "%d%d" , &n , &q ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d%d" , &a[ i ] , &b[ i ] ) ;
        v.push_back ( make_pair ( max ( a[ i ] , b[ i ] ) , i ) ) ;
    }
    for ( i = 1 ; i <= q ; i ++ ) {
        scanf ( "%d" , &x[ i ] ) ;
        srt[ i ] = make_pair ( x[ i ] , i ) ;
    }
    sort ( v.begin ( ) , v.end ( ) ) ;
    sort ( srt + 1 , srt + q + 1 ) ;
}

void solve ( ) {
    u.init ( 1 , 1 , q ) ;
    int i , pos ;
    pos = 1 ;
    for ( i = 0 ; i < n ; i ++ ) {
        while ( pos <= q && srt[ pos ].first < v[ i ].first ) {
            u.update ( 1 , 1 , q , srt[ pos ].second ) ;
            pos ++ ;
        }
        lst[ v[ i ].second ] = u.find ( 1 , 1 , q , min ( a[ v[ i ].second ] , b[ v[ i ].second ] ) ) ;
    }
    w.init ( 1 , 1 , q ) ;
    long long ans = 0 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        int br = w.query ( 1 , 1 , q , lst[ i ] + 1 , a[ i ] ) ;
        if ( lst[ i ] != 0 ) {
            if ( a[ i ] < b[ i ] ) { swap ( a[ i ] , b[ i ] ) ; }
        }
        if ( ( br % 2 ) == 1 ) {
            swap ( a[ i ] , b[ i ] ) ;
        }
        ans += a[ i ] ;
    }
    printf ( "%lld\n" , ans ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message

fortune_telling2.cpp: In function 'void input()':
fortune_telling2.cpp:127:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &q ) ;
                                ^
fortune_telling2.cpp:130:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d" , &a[ i ] , &b[ i ] ) ;
                                              ^
fortune_telling2.cpp:134:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &x[ i ] ) ;
                                  ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23264 KB Output is correct
2 Correct 3 ms 23264 KB Output is correct
3 Correct 3 ms 23264 KB Output is correct
4 Correct 6 ms 23264 KB Output is correct
5 Correct 3 ms 23264 KB Output is correct
6 Correct 6 ms 23264 KB Output is correct
7 Correct 6 ms 23264 KB Output is correct
8 Correct 9 ms 23264 KB Output is correct
9 Correct 3 ms 23264 KB Output is correct
10 Correct 6 ms 23264 KB Output is correct
11 Correct 6 ms 23264 KB Output is correct
12 Correct 9 ms 23264 KB Output is correct
13 Correct 9 ms 23264 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24668 KB Output is correct
2 Correct 36 ms 26380 KB Output is correct
3 Correct 56 ms 27012 KB Output is correct
4 Correct 99 ms 29804 KB Output is correct
5 Correct 79 ms 29804 KB Output is correct
6 Correct 79 ms 29804 KB Output is correct
7 Correct 79 ms 29804 KB Output is correct
8 Correct 76 ms 29804 KB Output is correct
9 Correct 53 ms 29804 KB Output is correct
10 Correct 53 ms 29804 KB Output is correct
11 Correct 53 ms 29804 KB Output is correct
12 Correct 46 ms 29804 KB Output is correct
13 Correct 59 ms 29804 KB Output is correct
14 Correct 76 ms 29804 KB Output is correct
15 Correct 73 ms 29804 KB Output is correct
16 Correct 96 ms 29804 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 52308 KB Output is correct
2 Correct 296 ms 52676 KB Output is correct
3 Correct 343 ms 53176 KB Output is correct
4 Correct 323 ms 54196 KB Output is correct
5 Correct 203 ms 52176 KB Output is correct
6 Correct 433 ms 54196 KB Output is correct
7 Correct 399 ms 54196 KB Output is correct
8 Correct 449 ms 54196 KB Output is correct
9 Correct 433 ms 54196 KB Output is correct
10 Correct 379 ms 54196 KB Output is correct
11 Correct 289 ms 54196 KB Output is correct
12 Correct 319 ms 54196 KB Output is correct
13 Correct 413 ms 54196 KB Output is correct
14 Correct 286 ms 54196 KB Output is correct
15 Correct 326 ms 54196 KB Output is correct
16 Correct 506 ms 54196 KB Output is correct
17 Correct 529 ms 54196 KB Output is correct
18 Correct 406 ms 54196 KB Output is correct
19 Correct 446 ms 54196 KB Output is correct
20 Correct 386 ms 54196 KB Output is correct