Submission #1100899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100899		hahahoang132	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	4 / 100	396 ms	46796 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define bit(x,y) ((x >> y) & 1)
const ll N = 2e5 + 5;
const ll inf = LLONG_MAX/4;
pair<ll,ll> t[N];
ll a[N],b[N],sus[20][N],haha[N];
ll siu[N],id[N];
vector<ll> messi[N];
ll maxr(ll l, ll r)
{
    ll sz = (r - l + 1);
    ll tmp = 1;
    ll cnt = 0;
    while(tmp * 2 <= sz)
    {
        tmp *= 2;
        cnt++;
    }
    return max(sus[cnt][l],sus[cnt][r - tmp + 1]);
}
struct segtree
{
    ll n;
    ll b[N * 4];
    void build(ll n)
    {
        this->n = n;
    }
    void udt(ll x)
    {
        b[x]++;
    }
    ll get(ll l, ll r)
    {
        ll ans = 0;
        ll i,j;
        for(i = l;i <= r;i++) ans += b[i];
        return ans;
    }
};
segtree f;
int main()
{
    ll n,q;
    cin >> n >> q;
    f.build(q);
    ll i,j;
    set<ll> tmp;
    for(i = 1;i <= n;i++)
    {
        cin >> a[i] >> b[i];
    }
    for(i = 1;i <= q;i++)
    {
        cin >> t[i].first;
        t[i].second = i;
    }
    sort(t + 1,t + 1 + q);
    for(i = 1;i <= q;i++)
    {
        id[t[i].second] = i;
        sus[0][i] = t[i].second;
    }
    for(i = 1;i < 20;i++)
    {
        for(j = 1;j <= q;j++)
        {
            sus[i][j] = max(sus[i - 1][j],sus[i - 1][j + (1 << (i - 1))]);
        }
    }
    for(i = 1;i <= n;i++)
    {
        ll s = min(a[i],b[i]);
        ll e = max(a[i],b[i]) - 1;
        if(s > t[q].first || t[1].first > e) continue;
        ll l = 1,r = q;
        ll k1,k2;
        while(true)
        {
            if(l == r)
            {
                k1 = l;
                break;
            }
            if(l + 1 == r)
            {
                if(t[l].first >= s) k1 = l;
                else k1 = r;
                break;
            }
            ll mid = (l + r) / 2;
            if(t[mid].first >= s) r = mid;
            else l = mid + 1;
        }
        l = 1;
        r = q;
        while(true)
        {
            if(l == r)
            {
                k2 = l;
                break;
            }
            if(l + 1 == r)
            {
                if(t[r].first <= e) k2 = r;
                else k2 = l;
                break;
            }
            ll mid = (l + r) / 2;
            if(t[mid].first <= e) l = mid;
            else r = mid - 1;
        }
        if(k1 > k2) haha[i] = 0;
        else haha[i] = maxr(k1,k2);
    }
    for(i = 1;i <= n;i++)
    {
        messi[haha[i]].push_back(i);
        //cout << haha[i] << " ";
    }
    for(i = q;i >= 0;i--)
    {
        for(auto x : messi[i])
        {
            if(i > 0)
            {
                if(a[x] < b[x])
                {
                    siu[x] = 1;
                }
            }

            ll e = max(a[x],b[x]);
            ll l = 1,r = q + 1;
            ll k;
            while(true)
            {
                if(l == r)
                {
                    k = l;
                    break;
                }
                if(l + 1 == r)
                {
                    if(e <= t[l].first) k = l;
                    else k = r;
                    break;
                }
                ll mid = (l + r)/ 2;
                if(e <= t[mid].first) r = mid;
                else l = mid + 1;
            }
            if(r == q + 1) continue;
            siu[x] += f.get(k,q);
        }
        if(i > 0) f.udt(id[i]);
    }
    ll ans = 0;
    for(i = 1;i <= n;i++)
    {
        if(siu[i] % 2 == 0) ans += a[i];
        else ans += b[i];
    }
    cout << ans;
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'long long int segtree::get(long long int, long long int)':
fortune_telling2.cpp:39:14: warning: unused variable 'j' [-Wunused-variable]
   39 |         ll i,j;
      |              ^

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