Submission #1100889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100889		proplayer	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	2 ms	10576 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],pre[maxN],suf[maxN];
int lg[maxN];
int n,k;
lli res;
void presp()
{
    lg[1] = 0;
    for (int i = 2;i <= n;++i) lg[i] = lg[i / 2] + 1;
    for (int j = 1;j < LG;++j)
        for (int i = 1;i <= n - (1 << j) + 1;++i)
        sp[j][i] = min(sp[j - 1][i],sp[j - 1][i + (1 << (j - 1))]);
}
int get(int l,int r)
{
    int k = lg[r - l + 1];
    return min(sp[k][l],sp[k][r - (1 << k) + 1]);
}
void input()
{
    cin >> n >> k;
    for (int i = 1;i <= n;++i) cin >> a[i] >> b[i];
    pre[0] = 0;
    for (int i = 1;i <= k;++i)
    {
        cin >> t[i];
        pre[i] = max(pre[i - 1],t[i]);
        sp[0][i] = t[i];
    }
    suf[k + 1] = 0;
    for (int i = k;i >= 1;--i) suf[i] = max(suf[i + 1],t[i]);
    presp();
}
void solve()
{
    for (int i = 1;i <= n;++i)
    {
        int mx = max(a[i],b[i]),mn = min(a[i],b[i]);
        if (pre[k] < a[i]) res += a[i];
        else if (pre[k] < b[i]) res += b[i];
        else
        {
            int id,id1;
            int l = 1,r = k;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (pre[mid] >= mx)
                {
                    l = mid + 1;
                    id = mid;
                }
                else r = mid - 1;
            }
            l = 1;r = id;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (get(mid,id) >= mx)
                {
                    r = mid - 1;
                    id1 = mid;
                }
                else l = mid + 1;
            }
            lli tmp;
            if ((id - id1 + 1) % 2 == 0) tmp = mx;
            else tmp = mn;
            if (pre[id1 - 1] < mn && mn == a[i]) tmp = tmp ^ mx ^ mn;
            if (suf[id + 1] >= mn) tmp = mx;
            res += tmp;
            //if (i == 1) cout << id1 << " " << id << "\n";
        }
    }
    cout << res;
}

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:74:25: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |             if (pre[id1 - 1] < mn && mn == a[i]) tmp = tmp ^ mx ^ mn;
      |                     ~~~~^~~
fortune_telling2.cpp:72:21: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |             if ((id - id1 + 1) % 2 == 0) tmp = mx;
      |                  ~~~^~~~~

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