Submission #209696

#	Time	Username	Problem	Language	Result	Execution time	Memory
209696		DodgeBallMan	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	5 ms	376 KiB

fortune_telling2

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second 

using namespace std;

const int N = 2e5 + 10;
int n, k, que[N], ans;
int seg[4*N], fen[N];
vector<int> coord;
vector<pii> quer, card;

void update( int pos, int val, int l = 1, int r = k, int idx = 1 ) {
    //printf("l %d r %d\n",l,r);
    if( l == r ) return void( seg[idx] = val );
    int mid = l + r >> 1;
    if( pos <= mid ) update( pos, val, l, mid, idx<<1 );
    else update( pos, val, mid+1, r, idx<<1|1 );
    seg[idx] = max( seg[idx<<1], seg[idx<<1|1] );
}

int query( int ll, int rr, int l = 1, int r = k, int idx = 1 ) {
    if( ll > rr ) return 0;
    if( l > rr || r < ll ) return 0;
    if( l >= ll && r <= rr ) return seg[idx];
    int mid = l + r >> 1;
    return max( query( ll, rr, l, mid, idx<<1 ), query( ll, rr, mid+1, r, idx<<1|1 ) );
}

void fup( int idx ) { for( int i = idx ; i < N ; i+= i & -i ) fen[i] += 1; }
int fque( int idx ) {
    int ret = 0;
    for( int i = idx ; i > 0 ; i -= i & -i ) ret += fen[i];
    return ret;
}

int main()
{
    scanf("%d %d",&n,&k);
    for( int i = 1, a, b ; i <= n ; i++ ) {
        scanf("%d %d",&a,&b);
        card.emplace_back( a, b );
    }
    for( int i = 1, a ; i <= k ; i++ ) {
        scanf("%d",&que[i]);
        coord.emplace_back( que[i] );
    }
    sort( coord.begin(), coord.end() );
    for( int i = 1 ; i <= k ; i++ ) {
        que[i] = lower_bound( coord.begin(), coord.end(), que[i] ) - coord.begin() + 1;
        //printf("%d %d\n",i,que[i]);
        update( que[i], i );
    }
    //printf("%d\n",query( 1, k ) );
    for( int i = 0 ; i < card.size() ; i++ ) {
        int a = min( card[i].x, card[i].y ), b = max( card[i].x, card[i].y );
        a = lower_bound( coord.begin(), coord.end(), a ) - coord.begin() + 1;
        b = upper_bound( coord.begin(), coord.end(), b-1 ) - coord.begin();
        int qq = query( a, b );
        //printf("%d %d %d %d\n",i,a,b,qq);
        if( qq ) 
            if( card[i].x < card[i].y ) swap( card[i].x, card[i].y );
        quer.emplace_back( qq, i );
    }
    sort( quer.begin(), quer.end(), greater<pii>() );
    int ptr = k;
    for( pii i : quer ) {
        //printf("%d %d\n",i.x,i.y);
        while( ptr > 0 && ptr > i.x ) {
            //printf("idx ptr%d %d\n",que[ptr],ptr);
            fup( que[ptr] );
            ptr--;
        }
        int b = max( card[i.y].x, card[i.y].y );
        int idx = lower_bound( coord.begin(), coord.end(), b ) - coord.begin();
        int cnt = fque( N-1 ) - fque( idx );
        //printf("%d\n",fque(N-1));
        //printf("idx%d cnt%d\n",idx,cnt);
        if( cnt % 2 ) swap( card[i.y].x, card[i.y].y );
        ans += card[i.y].x;
    }
    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void update(int, int, int, int, int)':
fortune_telling2.cpp:17:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
fortune_telling2.cpp: In function 'int query(int, int, int, int, int)':
fortune_telling2.cpp:27:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:45:21: warning: unused variable 'a' [-Wunused-variable]
     for( int i = 1, a ; i <= k ; i++ ) {
                     ^
fortune_telling2.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0 ; i < card.size() ; i++ ) {
                      ~~^~~~~~~~~~~~~
fortune_telling2.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&que[i]);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65