Submission #960398

#TimeUsernameProblemLanguageResultExecution timeMemory
960398pccFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
16 ms33372 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> #define _all(T) T.begin(),T.end() const int mxn = 6e5+10; int N,Q; vector<int> all; int rp[mxn]; pii range[mxn]; int arr[mxn]; namespace C1{ vector<pii> bit[mxn]; void add(int p,pii v){ for(;p<mxn;p+=p&-p){ bit[p].push_back(v); } return; } void getval(int p,int id){ for(int i = p;i>0;i-= i&-i){ while(!bit[i].empty()&&bit[i].back().fs>=p){ int now = bit[i].back().sc;bit[i].pop_back(); rp[now] = max(rp[now],id); } } return; } void GO(){ for(int i = 1;i<=N;i++){ if(range[i].fs == range[i].sc)continue; add(range[i].fs,pii(range[i].sc,i)); } for(int i = 1;i<mxn;i++)sort(bit[i].begin(),bit[i].end()); for(int i = Q;i>=1;i--){ getval(arr[i],i); } return; } } namespace C2{ ll ans = 0; int bit[mxn]; void modify(int p,int v){ for(;p<mxn;p+=p&-p)bit[p] += v; return; } int getval(int s,int e){ int re = 0; for(;e>0;e-= e&-e)re += bit[e]; s--; for(;s>0;s-= s&-s)re -= bit[s]; return re; } vector<int> op[mxn]; void GO(){ ans = 0; for(int i = 1;i<=N;i++){ op[rp[i]].push_back(i); } for(int i = Q;i>=0;i--){ for(auto &j:op[i]){ int cnt = getval(range[j].sc,mxn-1); ans += (cnt&1?all[range[j].sc]:all[range[j].fs]); } if(i)modify(arr[i],1); } cout<<ans<<'\n'; return; } } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N>>Q; all.push_back(-1); for(int i = 1;i<=N;i++){ cin>>range[i].fs>>range[i].sc; all.push_back(range[i].fs); all.push_back(range[i].sc); } for(int i = 1;i<=Q;i++){ cin>>arr[i]; all.push_back(arr[i]); } sort(all.begin(),all.end());all.resize(unique(all.begin(),all.end())-all.begin()); for(int i = 1;i<=N;i++){ range[i].fs = lower_bound(_all(all),range[i].fs)-all.begin(); range[i].sc = lower_bound(_all(all),range[i].sc)-all.begin(); } for(int i = 1;i<=Q;i++)arr[i] = lower_bound(_all(all),arr[i])-all.begin(); C1::GO(); C2::GO(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...