제출 #1286311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286311		iancunha	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	821 ms	32868 KiB

fortune_telling2

#include <bits/stdc++.h>
#define int int64_t
#define f first
#define s second
#define opt1 ios_base::sync_with_stdio(false)
#define opt2 cin.tie(NULL)
#define optimize opt1; opt2
#define pb push_back
#define endl "\n"
#define sz(v) (int)v.size()
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
typedef pair<ii, ii> i4;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<i3> vi3;
typedef vector<i4> vi4;
const int inf = 0x6f6f6f6f;
const int LOG = 22;
const int MAX = 200005;
const int mod = 1e9+7;

int a[MAX], b[MAX], T[MAX], T2[MAX], last[MAX], ans[MAX];

struct SEG {
    int seg[4*MAX];
    int join (int a, int b) { return max(a, b); }
    void upd (int no, int l, int r, int i, int v) {
        if (l == r) {
            seg[no] = v;
            return;
        }
        int m = (l+r)/2;
        if (i <= m) upd(2*no, l, m, i, v);
        else upd(2*no+1, m+1, r, i, v);
        seg[no] = join(seg[2*no], seg[2*no+1]);
    }
    int query (int no, int l, int r, int L, int R) {
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return seg[no];
        int m = (l+r)/2;
        return join(query(2*no,l,m,L,R),query(2*no+1,m+1,r,L,R));
    }
} seg;

struct BIT {
    int arv[MAX];
    int query (int x) {
        int res = 0;
        while (x > 0) {
            res += arv[x];
            x -= (x & -x);
        }
        return res;
    }
    int range (int l, int r) {
        return query(r) - query(l-1);
    }
    void upd (int x, int v) {
        while (x < MAX) {
            arv[x] += v;
            x += (x & -x);
        }
    }
} bit;

int LB (int high, int val) {
    int low = 1, mid, best = -1;
    while (low <= high) {
        mid = (low+high)/2;
        if (T2[mid] >= val) {
            best = mid;
            high = mid-1;
        } else low = mid+1;
    }
    return best;
}

map <int, int> M;

int32_t main () {
    optimize;
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    vi V;
    for (int i = 1; i <= k; i++) {
        cin >> T[i];
        T2[i] = T[i];
        V.pb(T[i]);
    }
    sort(T2+1, T2+k+1);
    sort(V.begin(), V.end());
    int cont = 1;
    for (auto v : V) M[v] = cont, cont++;
    for (int i = 1; i <= k; i++)
        seg.upd(1, 1, k, M[T[i]], i);
    vii Aux;    
    for (int i = 1; i <= n; i++) {
        int l = LB(k, min(a[i], b[i]));
        if (l == -1) {
            last[i] = 0;
            continue;
        }
        int r = LB(k, max(a[i],b[i]));
        if (r == 1) {
            last[i] = 0; 
            continue;
        } else if (r == -1) r = k;
        else r--;
        if (r < l) last[i] = 0;
        else last[i] = seg.query(1, 1, k, l, r);
    }
    for (int i = 1; i <= n; i++)
        if (last[i] > 0)    
            Aux.pb({last[i], i});
    sort(Aux.begin(), Aux.end());
    int p = 0;
    for (int i = 1; i <= k; i++) {
        bit.upd(M[T[i]], 1);
        while (p < sz(Aux) && Aux[p].f <= i) {
            int val = max(a[Aux[p].s], b[Aux[p].s]);
            if (LB(k, val) == -1) {
                p++;
                continue;
            }
            ans[Aux[p].s] = -bit.range(LB(k, val), k);
            p++;
        }
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        //cerr << last[i] << endl;
        int val = max(a[i], b[i]);
        if (LB(k, val) == -1) {
            if (a[i] >= b[i] || last[i] == 0)
                sum += a[i]; 
            else sum += b[i];
            continue;
        }
        //cerr << i << " " << ans[i] << " ";
        ans[i] += bit.range(LB(k, val), k);
        //cerr << ans[i] << endl;
        if (a[i] >= b[i] || last[i] == 0) {
            if (ans[i] % 2 == 0) sum += a[i];
            else sum += b[i];
        } else {
            if (ans[i] % 2 == 0) sum += b[i];
            else sum += a[i];
        }
    }
    cout << sum << endl;
    return 0;
}
/*
    cima >= baixo {
        T < baixo => nada
        T >= baixo e T < cima => cima
        T >= cima => baixo/cima
    }
    baixo > cima {
        T < cima => nada
        T >= cima e T < baixo => baixo
        T >= baixo => cima/baixo
    }

    => último cara >= min e < max
    pra cada A, B
    
*/

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