Submission #1016437

#TimeUsernameProblemLanguageResultExecution timeMemory
1016437AlishFortune Telling 2 (JOI14_fortune_telling2)C++17
100 / 100
315 ms37056 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define F first #define S second #define pb push_back #define endl '\n' #define Mp make_pair #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " = " << x << endl; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("tests.in" , "r" , stdin) ; ll mod = 1e9+7; const int N = 6e5+23; int seg[4*N], fen[N]; int a[N], b[N], t[N]; vector<int> in[N]; ll ans; int n, k, m; void upd(int i, int x, int l=1, int r=m+1, int ind=0){ if(r-l==1) { seg[ind]=x; return; } int mid=(r+l)>>1; if(i<mid) upd(i, x, l, mid, 2*ind+1); else upd(i, x, mid, r, 2*ind+2); seg[ind]=max(seg[2*ind+1], seg[2*ind+2]); } int get(int lx, int rx, int l=1, int r=m+1, int ind=0){ if(lx>=r || rx<=l) return 0; if(lx<=l && rx>=r) return seg[ind]; int mid=(r+l)>>1; return max(get(lx, rx, l, mid, 2*ind+1), get(lx, rx, mid, r, 2*ind+2)); } void uupd(int x, int v){ for(; x<N; x+=x&-x) fen[x]+=v; } int gget(int x){ int ans=0; for(; x>0; x-=x&-x) ans+=fen[x]; return ans; } int suff(int i){ return gget(N-1)-gget(i-1); } int main() { fast_io vector<int> vec; cin>>n>>k; for (int i=0; i<n; i++) { cin>>a[i]>>b[i]; vec.pb(a[i]); vec.pb(b[i]); } t[0]=1; for (int i=1; i<=k; i++) { cin>>t[i]; vec.pb(t[i]); } sort(all(vec)); vec.resize(unique(all(vec))-vec.begin()); m=vec.size(); for (int i=1; i<=k; i++){ t[i]=lower_bound(all(vec), t[i])-vec.begin()+1; upd(t[i], i); } for (int i=0; i<n; i++){ a[i]=lower_bound(all(vec), a[i])-vec.begin()+1; b[i]=lower_bound(all(vec), b[i])-vec.begin()+1; int num=get(min(a[i], b[i]), max(a[i], b[i])); if(num && b[i]>a[i]) swap(a[i], b[i]); in[num].pb(i); } for (int i=k; i>=0; i--){ for (int j: in[i]){ if(suff(max(a[j], b[j]))&1) swap(a[j], b[j]); ans+=vec[a[j]-1]; } uupd(t[i], 1); } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...