Submission #1216020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216020		alir3za_zar3	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	1 ms	576 KiB

fortune_telling2

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define     int     long long

const int maxn = 6e5+7;
int n,k , a[maxn],b[maxn],t[maxn];
struct SEGMENT
{
    int T[maxn<<2] = {};
    void update 
    (int id , int v , int node=1 , int l=0 , int r=maxn)
    {
        if (l+1 == r)
        {
            T[node] = v;
            return;
        }
        int o=l+r>>1 , lc=node<<1 , rc=lc|1;
        if (id<o) update(id , v , lc , l , o);
        else update(id , v , rc , o , r);
        T[node] = max(T[lc] , T[rc]);
    }
    int query 
    (int lq , int rq , int node=1 , int l=0 , int r=maxn)
    {
        if (r<=lq or l>=rq) return 0;
        if (lq<=l and r<=rq) return T[node];
        int o=l+r>>1 , lc=node<<1 , rc=lc|1;
        return max( query(lq , rq , lc , l , o),
                    query(lq , rq , rc , o , r));
    }
} seg;
struct FENWICK
{
    int bit[maxn];
    void update (int id)
    {
        for (; id<maxn; id+=id&-id)
            bit[id]++;
    }
    int query (int id)
    {
        int out = 0;
        for (; id; id-=id&-id)
            out += bit[id];
        return out;
    }
} fen;

signed main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    
    cin >> n >> k;
    vector<int> comp;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i] >> b[i];
        comp.push_back(a[i]);
        comp.push_back(b[i]);
    }
    for (int i=1; i<=k; i++)
    {
        cin >> t[i];
        comp.push_back(t[i]);
    }
    sort(comp.begin() , comp.end());
    comp.resize(unique(comp.begin(),comp.end())-comp.begin());
    unordered_map<int , int> mp , mq;
    int sz = comp.size();
    for (int i=0; i<sz; i++)
        mp[comp[i]] = i+1 , mq[i+1] = comp[i];
    set<pair<int,int> , greater<pair<int,int>>> pq;
    for (int i=1; i<=k; i++)
        seg.update(mp[t[i]] , i),
        pq.insert({mp[t[i]] , i});
    vector<pair<int,int>> q;
    for (int i=1; i<=n; i++)
        a[i] = mp[a[i]] , b[i] = mp[b[i]],
        q.push_back({max(a[i] , b[i]) , i});
    sort(q.begin() , q.end() , greater<pair<int,int>>());
    int out = 0;
    for (auto [s , id] : q)
    {
        while (!pq.empty())
        {
            auto [v , T] = *pq.begin();
            if (v < s) break;
            pq.erase(pq.begin());
            fen.update(T);
        }
        int z = (a[id]==b[id] ? 0:seg.query(min(a[id] , b[id]) , s));
        int val = fen.query(maxn-1)-(z?fen.query(z):0);
        if (z == 0)
            if (val%2) out += mq[b[id]];
            else out += mq[a[id]];
        else
            if (val%2 == 0) out += mq[s];
            else out += min(mq[a[id]] , mq[b[id]]);
    }
    cout << out << '\n';
}

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