Submission #1220520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220520		Khalid_Alabdullatif	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	1199 ms	118812 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const int N=6e5+1,mod=1e9+7;
int a[N],b[N],q[N];
int bignum[N];
int n,k;
struct vals{
	int mx,sum;
	vals(int m=0, int s=0){
		mx = m,sum = s;
	}
};
struct segtree{
	int n=0;
	vals t[4*N];
	segtree(int len){
		n=len;
	}
	vals merge(vals a, vals b){
		vals ans;
		ans.sum=a.sum+b.sum;
		ans.mx=max(a.mx,b.mx);
		return ans;
	}
	void update(int idx, int val,bool ok=1) {
		update(idx, val, ok, 1, n, 1);
	}
	void update(int idx,int val,bool ok,int l,int r,int node=1){
		if(l==r){
			if(ok)
				t[node].mx=t[node].sum=max(t[node].mx,val);
			else{
				t[node].sum+=val;
				t[node].mx+=val;
			}
			return;
		}
		int mid=(l+r)/2;
		if(idx<=mid)
			update(idx,val,ok,l,mid,node*2);
		else
			update(idx,val,ok,mid+1,r,node*2+1);
		t[node]=merge(t[node*2],t[node*2+1]);
	}
	vals get(int ql, int qr) {
		if(ql>qr)return vals();
		return get(ql, qr, 1, n);
	}
	vals get(int ql,int qr,int l,int r,int node=1){
		if(r<ql || qr<l)
			return 0;
		if(ql<=l && r<=qr)
			return t[node];
		int mid=(l+r)/2;
		return merge(get(ql,qr,l,mid,node*2),get(ql,qr,mid+1,r,node*2+1));
	}
};
unordered_map<int,int> mp,og;
void compress(){
    int cnt=1;
    set<int>s;
    for(int i=1;i<=n;i++){
    	s.insert(a[i]);
    	s.insert(b[i]);
    }
    for(int i=1;i<=k;i++)
    	s.insert(q[i]);
    for(auto i:s){
        og[cnt]=i;
        mp[i]=cnt++;
    }
    vector<pair<int,int>> v;
    for(int i=1;i<=n;i++){
        a[i]=mp[a[i]];
        b[i]=mp[b[i]];
    }
    vector<pair<int,int>> vec;
    for(int i=1;i<=k;i++){
        q[i]=mp[q[i]];
    }
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   	cin>>n>>k;
   	for(int i=1;i<=n;i++)
   		cin>>a[i]>>b[i];
   	for(int i=1;i<=k;i++)
   		cin>>q[i];
   	compress();
   	segtree rb(N),t(N);
   	for(int i=k;i>0;i--){
   		bignum[i]=rb.get(q[i],N).sum;
   		rb.update(q[i],1,0);
   		t.update(q[i],i);
   	}
   	int q1[k+1];
   	for(int i=1;i<=k;i++)
   		q1[i]=q[i];
   	sort(q1,q1+k+1);
   	ll ans=0;
   	for(int i=1;i<=n;i++){
   		int mn=min(a[i],b[i]),mx=max(a[i],b[i]);
   		int idx=t.get(mn,mx-1).mx;
   		if(idx==0){
   			idx=lower_bound(q1,q1+k+1,mx)-q1-1;
   			idx=k-idx;
   			if(idx%2)
   				ans+=og[b[i]];
   			else
   				ans+=og[a[i]];
   		}
   		else{
   			if(bignum[idx]%2)
   				ans+=og[mn];
   			else
   				ans+=og[mx];
   		}
   	}
   	cout<<ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65