제출 #209698

#제출 시각아이디문제언어결과실행 시간메모리
209698DodgeBallManFortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
434 ms9960 KiB
#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];
long long 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 += ( long long )card[i.y].x;
        //printf("%d %d\n",i.y,card[i.y].x);
    }
    printf("%lld",ans);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In function 'void update(int, int, int, int, int)':
fortune_telling2.cpp:18: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:28:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:46:21: warning: unused variable 'a' [-Wunused-variable]
     for( int i = 1, a ; i <= k ; i++ ) {
                     ^
fortune_telling2.cpp:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0 ; i < card.size() ; i++ ) {
                      ~~^~~~~~~~~~~~~
fortune_telling2.cpp:41: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:43: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:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&que[i]);
         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...