Submission #864152

#TimeUsernameProblemLanguageResultExecution timeMemory
864152ngonhatminFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
3 ms16988 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define FOR(i,a,b) for (int i=(a); i<=(b); ++i) #define FORD(i,a,b) for (int i=(a); i>=(b); --i) #define pb push_back #define pf push_front #define mp make_pair #define TWO(x) (1<<(x)) #define BIT(s,i) (((s)&TWO(i))>0) #define ON(s,i) (s |= TWO(i)) #define OFF(s,i) (s &= ~TWO(i)) #define FLIP(s,i) (s ^= TWO(i)) #define vvec vector<vector<int>> struct ngocon{ int val,lazy; }; struct point{ int x,y; }; typedef pair<int,int> pii; typedef pair<pii,int> piii; typedef pair<int,pii> ipii; typedef pair<pii,pii> pipi; const int h4[4] = {1,0,-1,0}; /// 4 huong const int c4[4] = {0,1,0,-1}; /// 4 huong const int h8[8] = {-1,-1,-1,0,1,1,1,0}; /// 8 huong const int c8[8] = {-1,0,1,1,1,0,-1,-1}; /// 8 huong const int cv1[8] = {1,2,2,1,-1,-2,-2,-1}; /// 8 huong quan ma const int cv2[8] = {-2,-1,1,2,2,1,-1,-2}; /// 8 huong quan ma const int mod = 1e9 + 7; /// chia du const int base = 26; /// ma hoa const int oo = 1e16; const int N = 2e5 + 2; int n,k,result; int a[N],b[N],v[N],f[24*N],d[N],bit[6*N],ans[N]; bool dd[N]; vector <int> nor,vec[N]; unordered_map <int,int> Map; void compress(){ FOR(i,1,n) nor.pb(a[i]), nor.pb(b[i]); FOR(i,1,k) nor.pb(v[i]); sort(nor.begin(),nor.end()); int pos; FOR(i,1,n){ pos = lower_bound(nor.begin(),nor.end(),a[i]) - nor.begin() + 1; Map[pos] = a[i]; a[i] = pos; pos = lower_bound(nor.begin(),nor.end(),b[i]) - nor.begin() + 1; Map[pos] = b[i]; b[i] = pos; } FOR(i,1,k) v[i] = lower_bound(nor.begin(),nor.end(),v[i]) - nor.begin() + 1; } void update(int i, int l, int r, int u, int v){ if (r < u || u < l) return; if (l == r){ f[i] = max(f[i],v); return; } int mid = (l + r) >> 1; update(i*2,l,mid,u,v); update(i*2+1,mid+1,r,u,v); f[i] = max(f[i*2],f[i*2+1]); } int query(int i, int l, int r, int u, int v){ if (r < u || v < l || u > v) return 0; if (u <= l && r <= v) return f[i]; int mid = (l + r) >> 1; return max(query(i*2,l,mid,u,v),query(i*2+1,mid+1,r,u,v)); } void update_bit(int i, int v){ while (i <= 6*n){ bit[i] += v; i += (i & (-i)); } } int query_bit(int i){ int res = 0; while (i > 0){ res += bit[i]; i -= (i & (-i)); } return res; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("input.txt","r",stdin); //freopen("ac.txt","w",stdout); cin >> n >> k; FOR(i,1,n) cin >> a[i] >> b[i]; FOR(i,1,k) cin >> v[i]; compress(); // FOR(i,1,n) cout << a[i] << ' ' << b[i] << '\n'; // FOR(i,1,k) cout << v[i] << ' '; cout << '\n'; FOR(i,1,k){ update(1,1,6*n,v[i],i); update_bit(v[i],1); } // cout << "end update" << '\n'; FOR(i,1,n){ // cout << i << ": " << min(a[i],b[i]) << ' ' << max(a[i],b[i]) - 1 << '\n'; d[i] = query(1,1,6*n,min(a[i],b[i]),max(a[i],b[i]) - 1); if (d[i] != 0) dd[i] = 1; vec[d[i]+1].pb(i); } // cout << "mmb" << '\n'; // // FOR(i,1,n) cout << d[i] << ' '; cout << '\n'; FOR(i,1,k){ // cout << i << '\n'; for (auto j : vec[i]) ans[j] = k - i + 1 - query_bit(b[j] - 1); update_bit(v[i],-1); } // cout << "ans: "; FOR(i,1,n) cout << ans[i] << ' '; cout << '\n'; FOR(i,1,n){ a[i] = Map[a[i]]; b[i] = Map[b[i]]; } FOR(i,1,n){ if (!dd[i]){ if (ans[i]%2 == 0) result += a[i]; else result += b[i]; } else{ if (a[i] >= b[i]){ if (ans[i]%2 == 0) result += a[i]; else result += b[i]; } else{ if (ans[i]%2 == 0) result += b[i]; else result += a[i]; } } } cout << result; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...