Submission #701025

#	Time	Username	Problem	Language	Result	Execution time	Memory
701025		hyakup	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	446 ms	22228 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn = 2e5 + 10;
const int inf = 1e9 + 10;
int bit[maxn], seg[4*maxn];

void updateBIT( int id ){ for( int i = id; i < maxn; i += i&-i ) bit[i]++; }
int queryBIT( int id ){
    int resp = 0;
    for( int i = id; i > 0 ; i -= i&-i ) resp += bit[i];
    return resp;
}

void updateSEG( int pos, int ini, int fim, int id, int val ){
    
    if( ini > id || id > fim ) return;
    if( ini == fim ){ seg[pos] = val; return; }
    int mid = ( ini + fim )/2;
    int l = 2*pos, r = 2*pos + 1;
    updateSEG( l, ini, mid, id, val );
    updateSEG( r, mid + 1, fim, id, val );
    seg[pos] = max( seg[l], seg[r] );
}

int querySEG( int pos, int ini, int fim, int ki, int kf ){
    if( ki > kf ) return 0;
    
    if( fim < ki || kf < ini ) return -inf;
    if( ki <= ini && fim <= kf ) return seg[pos];
    int mid = ( ini + fim )/2;
    int l = 2*pos, r = 2*pos + 1;
    int queryl = querySEG( l, ini, mid, ki, kf );
    int queryr = querySEG( r, mid + 1, fim, ki, kf );
    return max( queryl, queryr );
}

struct card{
    
    int maior, menor, idmaior;
    int a, b;
    card( int maior = 0, int menor = 0, int a = 0, int b = 0 ) : maior(maior), menor(menor), a(a), b(b) {}
    
};

vector<card> cartas;

struct evento{
    
    int val, id, tipo; 
    evento( int v, int i, int t ) : val(v), id(i), tipo(t) {}
    
    bool operator < ( evento e ){
        if( val == e.val ) return tipo > e.tipo;
        return val > e.val;
    }
};

vector<evento> lineSweep;

int main(){
    
    int n, m; cin >> n >> m;
    cartas.emplace_back();
    for( int i = 1; i <= n; i++ ){
        int a, b; cin >> a >> b;
        
        cartas.push_back( card( max( a, b ), min( a, b ), a, b ) );
        lineSweep.push_back( evento( max( a, b ), i, 2 ) );
        lineSweep.push_back( evento( min( a, b ), i, 1 ) );
    }
    
    for( int i = 1; i <= m; i++ ){
        int t; cin >> t;
        lineSweep.push_back( evento( t, i, 3 ) );
    }
    sort( lineSweep.begin(), lineSweep.end() );
    
    int cont = 0;
    ll resp = 0;
    for( evento cur : lineSweep ){
        
        if( cur.tipo == 3 ){
            updateBIT( cur.id );
            updateSEG( 1, 1, m, ++cont, cur.id );
        }
        if( cur.tipo == 2 ){
            cartas[ cur.id ].idmaior = cont + 1;
        }
        if( cur.tipo == 1 ){
            int last = querySEG( 1, 1, m, cartas[cur.id].idmaior, cont );
            int qtd = cont - queryBIT( last );
            
            if( last != 0 ){
                if( qtd%2 == 1 ){
                    resp += (ll)( cartas[cur.id].menor );
                } 
                else{
                    resp += (ll)( cartas[cur.id].maior );
                } 
            }
            else{
                if( qtd%2 == 1 ){
                    resp += (ll)( cartas[cur.id].b );
                } 
                else{
                    resp += (ll)( cartas[cur.id].a );
                } 
            }
            
        } 
        
    }
    
    cout << resp << endl;
}

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