Submission #317603

#	Time	Username	Problem	Language	Result	Execution time	Memory
317603		ThaiBaHung	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	679 ms	56536 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
const int N = 7e5 + 3;
int n, k;
struct ok2
{
    long long A;
    long long B;
    int cs;
};
ok2 a[N];
int pos[N][3];
int b[N];
int pos2[N];

vector < pair < int, int > > num;
pair < int, int > roirac[N];

struct ok
{
    int lo;
    int hi;
    int pos;
    int cnt;
};
ok Node[4 * N], Sum[4 * N];

void build(int id, int l, int r, ok Node[])
{
    Node[id].lo = l; Node[id].hi = r;
    if (l == r) return;
    int mid = (l + r) / 2;

    build(id * 2,l, mid, Node);
    build(id * 2 + 1, mid + 1, r, Node);
}

void update(int id, int val, int pos, ok Node[])
{
    if (Node[id].lo > pos || Node[id].hi < pos) return;

    if (Node[id].lo == Node[id].hi)
    {
        Node[id].pos = val;
        Node[id].cnt = 1;
        return;
    }

    update(id * 2, val, pos, Node);
    update(id * 2 + 1, val, pos, Node);

    Node[id].pos = max(Node[id * 2].pos, Node[id * 2 + 1].pos);
    Node[id].cnt = Node[id * 2].cnt + Node[id * 2 + 1].cnt;
}

int getpos(int id, int l, int r)
{
    if (l > r) return 0;
    if (Node[id].lo > r || Node[id].hi < l) return 0;

    if (l <= Node[id].lo && Node[id].hi <= r)
        return Node[id].pos;

    return max(getpos(id * 2,l,r), getpos(id * 2 + 1,l,r));
}

int getsum(int id, int pos)
{
    if (Sum[id].hi < pos) return 0;

    if (Sum[id].lo >= pos)
        return Sum[id].cnt;

    return getsum(id * 2, pos) + getsum(id * 2 + 1, pos);
}

bool cmp(ok2 a, ok2 b)
{
    return max(a.A, a.B) > max(b.A, b.B);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("t.inp","r",stdin); freopen("t.out","w",stdout);

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].A >> a[i].B;
        num.push_back({a[i].A,i});
        num.push_back({a[i].B,i});
        a[i].cs = i;
    }

    for (int i = 1; i <= k; i++)
    {
        cin >> b[i];
        num.push_back({b[i],i + n});
        roirac[i].first = b[i];
        roirac[i].second = i;
    }

    sort(num.begin(), num.end());

    int m = num.size();
    int dem = 1;

    for (int i = 0; i < m; i++)
    {
        int cur = num[i].first;
        int vt = num[i].second;

        if (i >= 1 && cur != num[i - 1].first) dem++;

        if (vt <= n)
        {
            if (pos[vt][1]) pos[vt][2] = dem;
            else
                if (pos[vt][2]) pos[vt][1] = dem;
                else
                    if (a[vt].A > a[vt].B) pos[vt][2] = dem;
                    else pos[vt][1] = dem;
        }
        else
            pos2[vt - n] = dem;
    }

    build(1,1,k,Sum);
    build(1,1,m,Node);

    sort(a + 1, a + n + 1, cmp);

    for (int i = 1; i <= k; i++)
        update(1,i,pos2[i],Node);

    sort(roirac + 1, roirac + k + 1);

    int lo = k;

    long long res = 0;

//    for (int i = 1; i <= n; i++)
//    {
//        cout << a[i].A << " " << a[i].B << '\n';
//    }

    for (int i = 1; i <= n; i++)
    {
        while (lo && roirac[lo].first >= max(a[i].A, a[i].B))
        {
            update(1,1,roirac[lo].second,Sum);
            lo--;
        }

        int vt = getpos(1, min(pos[a[i].cs][1], pos[a[i].cs][2]), max(pos[a[i].cs][1], pos[a[i].cs][2]) - 1);

        int bonus = 0;
        if (vt && a[i].A < a[i].B) bonus = 1;

        int to = getsum(1, vt + 1);
        //cout << getsum(1,10) << '\n';
        //cout << min(pos[a[i].cs][1], pos[a[i].cs][2]) << " " << max(pos[a[i].cs][1], pos[a[i].cs][2]) - 1 << ' ';
        //cout << bonus << " " << vt << " " << to << ' ';

        if ((to + bonus) % 2)
        {
            res += a[i].B;
            //cout << a[i].B << '\n';
        }
        else
        {
            res += a[i].A;
            //cout << a[i].A << '\n';
        }
    }

    cout << res;
}

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