Submission #49626

#TimeUsernameProblemLanguageResultExecution timeMemory
49626mra2322001Fortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
2039 ms30508 KiB
#include <bits/stdc++.h> #define f0(i, n) for(int i=(0); i<n; i++) #define f1(i, n) for(int i=(1); i<=n; i++) using namespace std; typedef long long ll; const int N = 200002; ll a[N], b[N], c[N], t[N][18]; int n, k, answer[N]; void rmq(){ f1(i, k) t[i][0] = c[i]; int l = log2(k); f1(j, l){ int u = (1 << j); for(int i = 1; i <= n - u + 1; i++){ t[i][j] = max(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]); } } } int get1(int u, int v){ if(u==0) ++u; if(u > v) return 0; int x = log2(v - u + 1); int res = max(t[u][x], t[v - (1 << x) + 1][x]); return res; } int Ans(int x){if(x==1) return 2;return 1;} main(){ ios_base::sync_with_stdio(0); cin >> n >> k; f1(i, n){ cin >> a[i] >> b[i]; } f1(i, k){ cin >> c[i]; } rmq(); vector <pair <int, int> > save; f1(i, n){ /// assume a[i] could be ans[1] /// find 1 and 2 while(save.size()) save.pop_back(); int k1 = k, k2 = k; while(1){ int p1, p2; int l = 1, r = k1, ans = 0; while(l <= r){ int mid = (l + r)/2; if(get1(mid, k1) >= a[i]) ans = mid, l = mid + 1; else r = mid - 1; } p1 = ans; l = 1, r = k2, ans = 0; while(l <= r){ int mid = (l + r)/2; if(get1(mid, k2) >= b[i]) ans = mid, l = mid + 1; else r = mid - 1; } p2 = ans; save.push_back(make_pair(p1, p2)); if(p1 != p2) break; if(p1==0) break; k1 = p1 - 1, k2 = p2 - 1; } int y = 2; /// now i belong to Ans(2) if(save.size() == 1){ if(save[0].first >= save[0].second) answer[i] = Ans(1); else answer[i] = Ans(2); } else{ for(int j = save.size() - 1; j >= 0; j--){ if(max(save[j].first, save[j].second)){ if(save[j].first==save[j].second){ if(y==2) y = 1; else y = 2; } else{ if(save[j].first > save[j].second){ y = 1; } else{ y = 2; } } } } answer[i] = Ans(y); } } ll res = 0; f1(i, n){ if(answer[i]==2) res += b[i]; else res += a[i]; } cout << res; }

Compilation message (stderr)

fortune_telling2.cpp:32:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...