Submission #215941

#TimeUsernameProblemLanguageResultExecution timeMemory
215941tselmegkhFortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
513 ms37092 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 6e5 + 5, inf = 1e9; #define pb push_back #define mp make_pair #define ll long long #define ff first #define ss second #define all(a) a.begin(),a.end() #define sz(x) (int)x.size() typedef vector<int> vi; typedef pair<int,int> ii; typedef vector<ii> vii; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int a[N], b[N], t[N], st[4 * N], bit[N], n, k, siz; vi q[N]; void update(int v, int l, int r, int idx, int x){ if(l > idx || r < idx)return; if(l == idx && r == idx){ st[v] = x; return; } int mid = (l + r) / 2; update(v * 2, l, mid, idx, x); update(v * 2 + 1, mid + 1, r, idx, x); st[v] = max(st[v * 2], st[v * 2 + 1]); } int query(int v, int l, int r, int ql, int qr){ if(l > qr || r < ql)return 0; if(l >= ql && r <= qr)return st[v]; int mid = (l + r) / 2; return max(query(v * 2, l, mid, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr)); } void add(int i){ if(!i)return; while(i <= siz){ bit[i]++; i += (i & (-i)); } } int sum(int i){ int res = 0; while(i > 0){ res += bit[i]; i -= (i & (-i)); } return res; } int rangesum(int l, int r){ return sum(r) - sum(l - 1); } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> n >> k; vi v; for(int i = 1; i <= n; i++){ cin >> a[i] >> b[i]; v.pb(a[i]); v.pb(b[i]); } for(int i = 1; i <= k; i++){ cin >> t[i]; v.pb(t[i]); } sort(all(v)); v.resize(distance(v.begin(), unique(all(v)))); siz = v.size(); for(int i = 1; i <= k; i++){ t[i] = lower_bound(all(v), t[i]) - v.begin() + 1; update(1, 1, siz, t[i], i); } ll ans = 0; for(int i = 1; i <= n; i++){ if(a[i] == b[i]){ ans += a[i]; continue; } a[i] = lower_bound(all(v), a[i]) - v.begin() + 1; b[i] = lower_bound(all(v), b[i]) - v.begin() + 1; int mx = query(1, 1, siz, min(a[i], b[i]), max(a[i], b[i]) - 1); if(mx && a[i] < b[i])swap(a[i], b[i]); q[mx].pb(i); } for(int i = k; i >= 0; i--){ for(auto x : q[i]){ int cnt = rangesum(max(a[x], b[x]), siz); if(cnt & 1){ swap(a[x], b[x]); } ans += v[a[x] - 1]; } add(t[i]); } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...