Submission #1205052

#TimeUsernameProblemLanguageResultExecution timeMemory
1205052PlayVoltzFortune Telling 2 (JOI14_fortune_telling2)C++20
100 / 100
306 ms33300 KiB
#include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> using namespace std; #define int long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second int q; vector<int> ft; int qq(int i){ int sum=0; for (;i;i-=i&(-i))sum+=ft[i]; return sum; } void up(int i, int val){ for (;i<=q;i+=i&(-i))ft[i]+=val; } struct node{ int s, e, m, val; node *l, *r; node(int S, int E){ s = S, e = E, m = (s+e)/2; val=0; if (s!=e){ l = new node(s, m); r = new node(m+1, e); } } void up(int ind, int nv){ if (s==e)val=nv; else{ if (ind<=m)l->up(ind, nv); else r->up(ind, nv); val = max(l->val, r->val); } } int query(int left, int right){ if (s==left && e==right)return val; if (right<=m)return l->query(left, right); else if (left>m)return r->query(left, right); else return max(l->query(left, m), r->query(m+1, right)); } }*st; bool custom(pii a, pii b){ return max(a.fi, a.se)<max(b.fi, b.se); } int32_t main(){ int n, ans=0; cin>>n>>q; vector<pii> vect(n), query(q); ft.resize(q+1, 0); st = new node(0, q-1); for (int i=0; i<n; ++i)cin>>vect[i].fi>>vect[i].se; for (int i=0; i<q; ++i)cin>>query[i].fi, query[i].se=i+1, up(i+1, 1); sort(query.begin(), query.end()); sort(vect.begin(), vect.end(), custom); for (int i=0; i<q; ++i)st->up(i, query[i].se); for (int i=0, p=0; i<n; ++i){ while (p<q&&query[p].fi<max(vect[i].fi, vect[i].se))up(query[p].se, -1), ++p; if (!p||query[p-1].fi<min(vect[i].fi, vect[i].se))ans+=((q-p)%2?vect[i].se:vect[i].fi); else{ int low=-1, high=p; while (low+1<high){ int mid=(low+high)/2; if (query[mid].fi>=min(vect[i].fi, vect[i].se))high=mid; else low=mid; } ans+=((qq(q)-qq(st->query(high, p-1)))%2?min(vect[i].fi, vect[i].se):max(vect[i].fi, vect[i].se)); } } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...