Submission #845994

#TimeUsernameProblemLanguageResultExecution timeMemory
845994dungzFortune Telling 2 (JOI14_fortune_telling2)C++17
100 / 100
1193 ms141560 KiB
#pragma GCC optimize ("O2") #include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define endl '\n' #define task "task" #define task "swapcard" #define prll pair<ll,ll> #define pb push_back #define ld long double #define int ll const ll MIN=-1e18,MAX=1e18,MOD=1e9+7; vector<int> f[800005]; int tree[3000005]; map<ll,int> danh; int d=0; pair<ll,ll> a[200005]; ll t[200005]; ll rev[1000005]; void build(ll node,ll l,ll r){ if(l==r) {f[node].push_back(t[l]);return;} ll m=(l+r)/2; build(node*2,l,m); build(node*2+1,m+1,r); merge(f[node*2].begin(),f[node*2].end(),f[node*2+1].begin(),f[node*2+1].end(),back_inserter(f[node])); } ll chat(ll node,ll x){ ll l=0,r=f[node].size()-1,fl=-1; while(l<=r){ ll m=(l+r)/2; if(f[node][m]>=x){ fl=m; r=m-1; } else l=m+1; } return (fl==-1?0:f[node].size()-fl); } ll get(ll node,ll l,ll r,ll u,ll v,ll x){ if(l>v or r<u) return 0; if(l>=u and r<=v) return chat(node,x); ll m=(l+r)/2; return get(node*2,l,m,u,v,x)+get(node*2+1,m+1,r,u,v,x); } void update2(int node,int l,int r,int u,int v) { if(l>u or r<u) return; if(l==r) { tree[node]=v; return; } int m=(l+r)/2; update2(node*2,l,m,u,v); update2(node*2+1,m+1,r,u,v); tree[node]=max(tree[node*2],tree[node*2+1]); } int get2(int node,int l ,int r ,int u, int v) { if(l>v or r<u) return -1; if(l>=u and r<=v) return tree[node]; int m=(l+r)/2; return max(get2(node*2,l,m,u,v),get2(node*2+1,m+1,r,u,v)); } vector<ll> lst; signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,k; cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i].fi>>a[i].se; lst.push_back(a[i].fi); lst.push_back(a[i].se); } for(int i=1;i<=k;i++) { cin>>t[i]; lst.push_back(t[i]); } sort(lst.begin(),lst.end()); for(auto i:lst) { if(!danh[i]) { danh[i]=++d; rev[d]=i; } } for(int i=1;i<=n;i++) { a[i].fi=danh[a[i].fi]; a[i].se=danh[a[i].se]; } for(int i=1;i<=4*d;i++) { tree[i]=-1; } for(int i=1;i<=k;i++) { t[i]=danh[t[i]]; update2(1,1,d,t[i],i); } build(1,1,k); ll ans=0; for(int i=1;i<=n;i++) { int u=a[i].fi,v=a[i].se; if(u>v) swap(u,v); int pos=get2(1,1,d,u,v-1); // cout<<u<<" "<<v<<" "<<pos<<endl; if(pos==-1) { int sl=get(1,1,k,1,k,v); if(sl%2==0) ans+=rev[a[i].fi]; else ans+=rev[a[i].se]; // if(sl%2==0) cout<<a[i].fi<<endl; // else cout<<a[i].se; } else { int sl=get(1,1,k,pos,k,v); if(sl%2==0) ans+=rev[v]; else ans+=rev[u]; // if(sl%2==0) cout<<u<<endl; // else cout<<u<<endl; } // cout<<endl; } cout<<ans; } /* */

Compilation message (stderr)

fortune_telling2.cpp:9: warning: "task" redefined
    9 | #define task "swapcard"
      | 
fortune_telling2.cpp:8: note: this is the location of the previous definition
    8 | #define task "task"
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...