Submission #95304

#	Time	Username	Problem	Language	Result	Execution time	Memory
95304		bogdan10bos	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1754 ms	87588 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<int, int> pii;

const int NMAX = 2e5;

pii card[NMAX + 5];
int N, M, K;
int pos[NMAX + 5], v[NMAX + 5];
int lg2[3 * NMAX + 5], rmq[20][3 * NMAX + 5];
int ordC[NMAX + 5], ordV[NMAX + 5];

class Normalizer
{
public:
    vector<int> ord;
    map<int, int> mp;

    void add(int x) { if(mp.count(x)) return; mp[x]; ord.push_back(x); }
    void pre()
    {
        sort(begin(ord), end(ord));
        for(int i = 0; i < ord.size(); i++)
            mp[ ord[i] ] = i + 1;
    }
    int get(int x) { return mp[x]; }
}nrm;

class BinaryIndexedTree
{
public:
    int aib[NMAX + 5];
    void U(int pos)
    {
        for(; pos <= M; pos += (pos & (-pos)))
            aib[pos]++;
    }
    int Q(int pos)
    {
        int ans = 0;
        for(; pos > 0; pos -= (pos & (-pos)))
            ans += aib[pos];
        return ans;
    }
}aib;

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        card[i] = {x, y};
        nrm.add(x); nrm.add(y);
    }
    for(int i = 1; i <= M; i++)
    {
        scanf("%d", &v[i]);
        nrm.add(v[i]);
    }
    nrm.pre();
    K = nrm.ord.size();
    for(int i = 1; i <= N; i++)
    {
        card[i].first = nrm.get(card[i].first);
        card[i].second = nrm.get(card[i].second);
    }
    for(int i = 1; i <= M; i++) v[i] = nrm.get(v[i]);
    for(int i = 1; i <= M; i++)
        rmq[0][ v[i] ] = i;
    for(int i = 2; i <= K; i++) lg2[i] = lg2[i >> 1] + 1;
    for(int i = 1; (1 << i) <= K; i++)
        for(int j = 1; j + (1 << i) - 1 <= K; j++)
            rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);

    for(int i = 1; i <= N; i++)
    {
        int st = min(card[i].first, card[i].second), dr = max(card[i].first, card[i].second) - 1;
        if(st > dr) { pos[i] = 0; continue; }
        int lg = lg2[dr - st + 1];
        pos[i] = max(rmq[lg][st], rmq[lg][dr - (1 << lg) + 1]);
    }

    for(int i = 1; i <= N; i++) ordC[i] = i;
    sort(ordC + 1, ordC + N + 1,
         [](int a, int b) { return max(card[a].first, card[a].second) > max(card[b].first, card[b].second); });
    for(int i = 1; i <= M; i++) ordV[i] = i;
    sort(ordV + 1, ordV + M + 1,
         [](int a, int b) { return v[a] > v[b]; });

    int p = 1;
    long long ans = 0LL;
    for(int i = 1; i <= N; i++)
    {
        int id = ordC[i];
        int val = max(card[id].first, card[id].second);
        while(p <= M && val <= v[ ordV[p] ])
        {
            aib.U(ordV[p]);
            p++;
        }

        int cnt = aib.Q(M) - aib.Q(pos[id]);
        int face = 0;
        if(pos[id] == 0)
        {
            if(cnt % 2 == 1)    face = card[id].second;
            else    face = card[id].first;
        }
        else
        {
            if(cnt % 2 == 1)    face = min(card[id].first, card[id].second);
            else    face = max(card[id].first, card[id].second);
        }
        face = nrm.ord[face - 1];
        ans += face;
    }

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void Normalizer::pre()':
fortune_telling2.cpp:27:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < ord.size(); i++)
                        ~~^~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &v[i]);
         ~~~~~^~~~~~~~~~~~~

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