Submission #1212333

#TimeUsernameProblemLanguageResultExecution timeMemory
1212333biankFortune Telling 2 (JOI14_fortune_telling2)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<int(n);i++) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define dforn(i,n) for(int i=int(n)-1;i>=0;i--) #define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--) #define fst first #define snd second #define pb push_back #define eb emplace_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() typedef long long ll; typedef vector<ll> vll; typedef vector<int> vi; typedef pair<int,int> ii; const int INF=1e9+20; const int N=2e5+9; int ft[N]; void upd(int p){ for(++p;p<N;p+=p&-p) ft[p]++; } int query(int p){ int s=0; for(;p>0;p-=p&-p) s+=ft[p]; return s; } int query(int l, int r){ return query(r)-query(l); } int main(){ ios::sync_with_stdio(0); cin.tie(0); int n,k; cin>>n>>k; vi a(n),b(n); forn(i,n) cin>>a[i]>>b[i]; vi t(k); forn(i,k) cin>>t[i]; vi suff_min(k+1),suff_max(k+1); suff_min[k]=INF,suff_max[k]=-INF; dforn(i,k){ suff_min[i]=min(suff_min[i+1],t[i]); suff_max[i]=max(suff_max[i+1],t[i]); } vector<tuple<int,int,int>> queries; forn(i,n){ auto[c,d]=minmax(a[i],b[i]); int lo=-1,hi=k; while(hi-lo>1){ int mid=(lo+hi)/2; if(suff_min[mid]>=d||suff_max[mid]<c) hi=mid; else lo=mid; } queries.eb(d,hi,i); } vi order(k); iota(all(order),0); sort(all(order),[&](const int &lhs, const int &rhs){ return t[lhs]>t[rhs]; }); sort(all(queries)); reverse(all(queries)); ll ret=0; int j=0; for(auto[d,p,i]:queries){ while(j<k&&t[order[j]]>=d) upd(order[j++]); bool f=query(p,k)%2; if(p==0){ if(f) ret+=b[i]; else ret+=a[i]; }else{ if(f) ret+=min(a[i],b[i]); else ret+=max(a[i],b[i]); } } cout<<ret<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...