Submission #1100984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100984		vjudge1	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	3067 ms	12624 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];
    for (int i = 1;i <= k;++i)
    {
        id[i] = i;
        cin >> t[i];
    }
    sort(id + 1,id + k + 1,cmp);
    presp();
}
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;
        }
        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) update(id[it],1);--it;
        res = getsum(q[i].first + 1,k);
        if (q[i].first == 0 && b[q[i].second] > a[q[i].second]) res--;
        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:107: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]
  107 |     for (int i = 0;i < q.size();++i)
      |                    ~~^~~~~~~~~~
fortune_telling2.cpp:109:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  109 |         while (t[id[it]] >= max(b[q[i].second],a[q[i].second]) && it >= 1) update(id[it],1);--it;
      |         ^~~~~
fortune_telling2.cpp:109:93: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  109 |         while (t[id[it]] >= max(b[q[i].second],a[q[i].second]) && it >= 1) update(id[it],1);--it;
      |                                                                                             ^~

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