Submission #751580

#TimeUsernameProblemLanguageResultExecution timeMemory
751580aebovFortune Telling 2 (JOI14_fortune_telling2)C++17
100 / 100
1745 ms48976 KiB
//#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O2") //#pragma GCC optimize("fast-math") #include<iostream> #include<vector> #include<cmath> #include<queue> #include<utility> #include<algorithm> #include<bitset> #include<map> #include<iomanip> #include<set> #include<string.h> #include<stack> #include <list> #include <numeric> #include <random> #include<unordered_map> #define all(x) x.begin(), x.end() #define ln (e-s+1) #define lc (id*2) #define rc (id*2 + 1) #define md ((e+s)/2) #define dm ((e+s)/2+1) #define pb push_back #define ll long long #define endl '\n' #define mk make_pair #define F first #define pll pair<ll, ll> #define S second #define pvv pair<vector<int> , vector<int> > #define pii pair<int,int> #define plll pair<ll, pair<int, int> > #define ld long double #define mat vector<vector<ll>> //#define int long long using namespace std; const int N = (int)2e5 + 5, mod = (int) 1e9 + 7; int n, k, a[N], b[N], t[N], mn, mx; vector<int> seg[N << 2]; void build(int id = 1,int s = 1,int e = k){ if(ln == 1){ seg[id].pb(t[s]); return; }build(lc, s, md), build(rc, dm, e); for(int x : seg[lc]) seg[id].pb(x); for(int x : seg[rc]) seg[id].pb(x); sort(seg[id].begin(), seg[id].end()); } pii get(int l2,int r2,int id = 1,int s = 1,int e = k){ if(l2 > e || r2 < s) return {mod, 0}; if( l2 <= s && e <= r2){ int l = 0, r = seg[id].size() - 1, ans = -1; while(l <= r){ int mid = (l+r) >> 1; if(seg[id][mid] >= mn) ans = mid, r = mid - 1; else l = mid + 1; } l = 0, r = seg[id].size() - 1;int ans2 = seg[id].size(); while(l <= r){ int mid = (l+r) >> 1; if(seg[id][mid] >= mx) ans2 = mid, r = mid - 1; else l = mid + 1; } if(ans == -1) return {mod , 0}; return {seg[id][ans], seg[id].size() - ans2}; } auto g1 = get(l2, r2, lc, s, md), g2 = get(l2, r2, rc, dm, e); return {min(g1.F, g2.F), g1.S + g2.S} ; } int main(){ // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); scanf("%d%d", &n, &k); for(int i = 1; i <= n; i ++) scanf("%d%d", &a[i], &b[i]); for(int i = 1; i <= k; i ++) scanf("%d", &t[i]); build(); ll ret = 0; for(int i = 1; i <= n; i ++){ int l = 1, r = k, ans = k+1; mn = min(a[i], b[i]), mx = max(a[i], b[i]); while(l <= r){ int mid = (l+r) >> 1; if(get(mid, k).F >= mx) ans = mid, r = mid - 1; else l = mid + 1; } // cout << "few : " << ans << endl; if(get(1, ans - 1).F < mx){ if(get(ans, k).S %2 == 0) ret += mx; else ret += mn; } else{ if(get(ans , k).S % 2 == 0) ret += a[i]; else ret += b[i]; } // cout << ret << endl; }printf("%lld\n", ret); }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:79:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  for(int i = 1; i <= n; i ++) scanf("%d%d", &a[i], &b[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:80:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  for(int i = 1; i <= k; i ++) scanf("%d", &t[i]);
      |                               ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...