제출 #1344133

#제출 시각아이디문제언어결과실행 시간메모리
1344133hoangtien69운세 보기 2 (JOI14_fortune_telling2)C++20
100 / 100
316 ms21400 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXX = 3 * MAXN;

int n, k;
int a[MAXN];
int b[MAXN];
int x[MAXN];
int y[MAXN];
vector<int> peal;
int query[MAXN];
int v[MAXX];
int st[4 * MAXX];
bool ck[MAXN];
vector<int> last[MAXN];
int bit[MAXX];

int get(int x)
{
    return lower_bound(peal.begin(), peal.end(), x) - peal.begin() + 1;
}
void update(int id, int l, int r, int pos, int val)
{
    if (l == r)
    {
        st[id] = val;
        return;
    }
    int m = (l + r) >> 1;
    if (pos <= m)
    {
        update(id << 1, l, m, pos, val);
    }
    else
    {
        update(id << 1 | 1, m + 1, r, pos, val);
    }
    st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v)
{
    if (v < l || r < u)
    {
        return 0;
    }
    if (u <= l and r <= v)
    {
        return st[id];
    }
    int m = (l + r) >> 1;
    return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
void update1(int pos, int val)
{
    for (int i = pos; i <= MAXX; i += i & -i)
    {
        bit[i] += val;
    }
}
int sum(int pos)
{
    int total = 0;
    for (int i = pos; i > 0; i -= i & -i)
    {
       total += bit[i];
    }
    return total;
}
int range(int l, int r)
{
    return sum(r) - sum(l - 1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        int minn = min(a[i], b[i]);
        int maxx = max(a[i], b[i]);
        x[i] = minn;
        y[i] = maxx;
        peal.push_back(a[i]);
        peal.push_back(b[i]);
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> query[i];
        peal.push_back(query[i]);
    }
    sort(peal.begin(), peal.end());
    peal.erase(unique(peal.begin(), peal.end()), peal.end());
    int sz = peal.size();
    for (int i = 1; i <= n; i++)
    {
        x[i] = get(x[i]);
        y[i] = get(y[i]);
    }
    for (int i = 1; i <= k; i++)
    {
        query[i] = get(query[i]);
    }
    for (int i = 1; i <= k; i++)
    {
        v[query[i]] = max(v[query[i]], i);
    }
    for (int i = 1; i <= sz; i++)
    {
        update(1, 1, sz, i, v[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        int cur = get(1, 1, sz, x[i], y[i] - 1);
        last[cur].push_back(i);
    }
    long long res = 0;
    for (int i = k; i >= 1; i--)
    {
        for (int pos : last[i])
        {
            int cak = range(y[pos], sz);
            if (cak % 2 == 0)
            {
                if (a[pos] >= b[pos])
                {
                    res += a[pos];
                }
                else
                {
                    res += b[pos];
                }
            }
            else
            {
                if (a[pos] >= b[pos])
                {
                    res += b[pos];
                }
                else
                {
                    res += a[pos];
                }
            }
        }
        update1(query[i], 1);
    }
    for (int pos : last[0])
    {
        int cur = range(y[pos], sz);
        if (cur % 2 == 0)
        {
            res += a[pos];
        }
        else
        {
            res += b[pos];
        }
    }
    cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...