Submission #1100884

#TimeUsernameProblemLanguageResultExecution timeMemory
1100884proplayerFortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
2 ms10584 KiB
#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 (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;
      |                  ~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...