Submission #636054

#TimeUsernameProblemLanguageResultExecution timeMemory
636054MasterTasterFortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
2 ms468 KiB
#include <iostream> #include <vector> #include <iterator> #include <algorithm> #define ll long long #define MAXN 200010 #define pii pair<int, int> #define xx first #define yy second #define pb push_back using namespace std; int n, k, a[MAXN], b[MAXN], t[MAXN], last[MAXN]; int cnt[MAXN]; int bit[4*MAXN+5], seg[12*MAXN]; bool sw[MAXN]; pii c[MAXN]; vector<pii> tmp; void build(int node, int l, int r) { if (l==r) { seg[node]=c[l].yy; return; } int mid=l+(r-l)/2; build(2*node, l, mid); build(2*node+1, mid+1, r); seg[node]=max(seg[2*node], seg[2*node+1]); } int maxQuery(int node, int l, int r, int levo, int desno) { if (levo>r || desno<l) return -1; if (levo<=l && desno>=r) return seg[node]; int mid=l+(r-l)/2; return max(maxQuery(2*node, l, mid, levo, desno), maxQuery(2*node+1, mid+1, r, levo, desno)); } void upd(int x, int val) { while (x<MAXN) { bit[x]+=val; x+=x&(-x); } return; } int sum(int x) { int ret=0; while (x) { ret+=bit[x]; x-=x&(-x); } return ret; } int main() { cin>>n>>k; for (int i=1; i<=n; i++) { cin>>a[i]>>b[i]; if (a[i]>b[i]) { sw[i]=true; swap(a[i], b[i]); } } for (int i=1; i<=k; i++) cin>>t[i]; for (int i=1; i<=k; i++) { pii par={t[i], i}; c[i]=par; } sort(c+1, c+k+1); ///for (int i=1; i<=k; i++) { cout<<c[i].xx<<" "<<c[i].yy<<endl; } build(1, 1, k); for (int i=1; i<=n; i++) { pii minpar = {a[i], 0}, maxpar = {b[i], 0}; int l = distance(c + 1, lower_bound(c + 1, c + k + 1, minpar)); int r = distance(c + 1, lower_bound(c + 1, c + k + 1, maxpar)); r--; l++; r++; ///cout<<i<<": "<<l<<" lr "<<r<<endl; if (l > r) last[i] = 0; else last[i] = maxQuery(1, 1, k, l, r); } for (int i=1; i<=n; i++) tmp.pb({last[i], i}); sort(tmp.begin(), tmp.end()/*, greater<pii>()*/); ///for (int i=0; i<tmp.size(); i++) cout<<tmp[i].xx<<" tmp "<<tmp[i].yy<<endl; int j=tmp.size()-1; for (int i=k; i>=0; i--) { ///cout<<"i "<<i<<endl; if (i) upd(t[i], 1); while (j>=0 && tmp[j].xx==i) { /*cout<<i<<" ij "<<j<<endl;*/ cnt[tmp[j].yy]=sum(a[tmp[j].yy]-1); j--; } ///cout<<j<<" j"<<endl; } ll ans=0; for (int i=1; i<=n; i++) { int kolko=k-last[i]-cnt[i]; if (last[i]==0 && sw[i]) swap(a[i], b[i]); ///cout<<i<<" "<<last[i]<<" "<<cnt[i]<<endl; if (last[i]==0) { if (kolko%2) ans+=b[i]; else ans+=a[i]; } else { if (kolko%2) ans+=a[i]; else ans+=b[i]; } } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...