Submission #1100982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100982		proplayer	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	264 ms	29992 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const int maxN = 2e5 + 5;
const int LG = 19;
int a[maxN],b[maxN],t[maxN];
int sp[LG][maxN];
int lg[maxN],id[maxN];
lli cnt[maxN],bit[maxN];
lli res;
int n,k;
vector<int> v;
vector<pair<int,int>> q;
void presp()
{
    lg[1] = 0;
    for (int i = 1;i <= k;++i) sp[0][i] = id[i];
    for (int i = 2;i <= k;++i) lg[i] = lg[i / 2] + 1;
    for (int j = 1;j < LG;++j)
        for (int i = 1;i <= k - (1 << j) + 1;++i)
        sp[j][i] = max(sp[j - 1][i],sp[j - 1][i + (1 << (j - 1))]);
}
int get(int l,int r)
{
    int k = lg[r - l + 1];
    return max(sp[k][l],sp[k][r - (1 << k) + 1]);
}
bool cmp(int x,int y)
{
    if (t[x] == t[y]) return x > y;
    return t[x] < t[y];
}
void input()
{
    cin >> n >> k;
    for (int i = 1;i <= n;++i)
    {
        cin >> a[i] >> b[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    for (int i = 1;i <= k;++i)
    {
        id[i] = i;
        cin >> t[i];
        v.push_back(t[i]);
    }
    sort(id + 1,id + k + 1,cmp);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    presp();
}
int getid(int x)
{
    return lower_bound(v.begin(),v.end(),x) + 1 - v.begin();
}
bool cmp1(pair<int,int> x,pair<int,int> y)
{
    return max(a[x.second],b[x.second]) > max(b[y.second],a[y.second]);
}
void update(int i,int val)
{
    while (i <= k)
    {
        bit[i] += val;
        i += (i & (-i));
    }
}
lli getsum(int l,int r)
{
    --l;
    lli res = 0;
    while (l > 0)
    {
        res -= bit[l];
        l -= (l & (-l));
    }
    while (r > 0)
    {
        res += bit[r];
        r -= (r & (-r));
    }
    return res;
}
void solve()
{
    for (int i = 1;i <= n;++i)
    {
        int mn = min(a[i],b[i]);
        int mx = max(a[i],b[i]);
        int l = 1,r = k,id1 = 0,id2 = 0;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (t[id[mid]] >= mn)
            {
                id1 = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        l = 1;r = k;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (t[id[mid]] < mx)
            {
                id2 = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        //cerr << get(id1,id2) << " " << b[i] << " " << id1 << " "  << id2 << "\n";
        if (id1 > id2 || id1 == 0 || id2 == 0) q.push_back({0,i});
        else q.push_back({get(id1,id2),i});
    }
    sort(q.begin(),q.end(),cmp1);
    int it = k;
    lli ans = 0;
    for (int i = 0;i < q.size();++i)
    {
        while (t[id[it]] >= max(b[q[i].second],a[q[i].second]) && it >= 1)
        {
            //cerr << max(b[q[i].second],a[q[i].second]) << " " << id[it] << " " << t[id[it]] << " "  << i << "\n";
            update(id[it],1);--it;
        }
        //cerr << getsum(q[i].first + 1,k) << "\n";
        //cout << q[i].first + 1 << " " << k << "A\n";
        res = getsum(q[i].first + 1,k);
        //cout << q[i].first <<  "\n";
        if (q[i].first == 0 && b[q[i].second] > a[q[i].second]) res--;
        //cout << res << "\n";
        if (res % 2 == 0) ans += max(b[q[i].second],a[q[i].second]);
        else ans += min(b[q[i].second],a[q[i].second]);
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("P1.inp","r",stdin);
    //freopen("P1.out","w",stdout);
    input();
    solve();
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void solve()':
fortune_telling2.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0;i < q.size();++i)
      |                    ~~^~~~~~~~~~

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