oj.uz

답안 #1100884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100884 2024-10-15T01:21:01 Z proplayer 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 2 ms 10584 KB 
#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);
    input();
    solve();
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -