Submission #31427

#	Time	Username	Problem	Language	Result	Execution time	Memory
31427		chonka	Fortune Telling 2 (JOI14_fortune_telling2)	C++98	100 / 100	529 ms	54196 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65