제출 #535452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535452		fadi57	운세 보기 2 (JOI14_fortune_telling2)	C++14	4 / 100	137 ms	29132 KiB

fortune_telling2

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int mx= 700 * 1000 + 3;
const int mx2=1e6+9;
typedef long long ll;
const int mod=998244353 ;
const int SQ=400;
const ll inf=1e9+10;
vector<int>cord,q[mx];
int seg[mx<<2],a[mx],b[mx],T[mx],aa[mx], bb[mx];
tree<int,null_type,greater_equal<int>,rb_tree_tag,tree_order_statistics_node_update> s;
int sz;int t;int n,k;
struct fenwick{
    int n, fen[600005];
    void resize(int _n){
        n = _n + 1;
        memset(fen, 0, sizeof fen);
    }
    int query(int ind){
        int ans = 0;
        while(ind >= 1){
            ans += fen[ind];
            ind -= ind & -ind;
        }
        return ans;
    }
    void update(int ind, ll val){
        while(ind <= n){
            fen[ind] += val;
            ind += ind & -ind;
        }
    }
    int query(int l, int r){
        return query(r) - query(l - 1);
    }
};
fenwick fen;
int combin(int x,int y){
  if(t==0){
    return (max(x,y));
  }else{
    return x+y;
  }

}
void update(int node,int l,int r,int idx,int val){
   if(l==r){
    seg[node]=val;
    return;
   }
    int mid=(l+r)/2;
    if(idx<=mid){
    update(node*2,l,mid,idx,val);
   }else{
    update(node*2+1,mid+1,r,idx,val);
   }
   seg[node]=combin(seg[node*2],seg[node*2+1]);
    return;
  }
  int query(int node,int l,int r,int left,int right){
         if(r<left||l>right){
            if(t){return 0;}
            return -1;
      }
  if(l>=left&&r<=right){
        return seg[node];
     }
     int mid=(l+r)/2;
     return combin(query(node*2,l,mid,left,right), query(node*2+1,mid+1,r,left,right));
     }


int fin(int x){
  return upper_bound(cord.begin(),cord.end(),x)-cord.begin();
  }

 int main(){
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    aa[i]=a[i];
    bb[i]=b[i];
    cord.push_back(a[i]);
    cord.push_back(b[i]);
  }
for(int i=0;i<k;i++){
     cin>>T[i];
     cord.push_back(T[i]);
  }
cord.erase(unique(cord.begin() , cord.end()) , cord.end()) ;sort(cord.begin(),cord.end());
sz=2*n+k;

for(int i=0;i<n;i++){
    a[i]=fin(a[i]);
    b[i]=fin(b[i]);
  }
   memset(seg,-1,sizeof(seg));
   for(int i=0;i<k;i++){
    T[i]=fin(T[i]);
    update(1,0,sz,T[i],i);
    }
  for(int i=0;i<n;i++){
    int idx=query(1,0,sz,min(a[i],b[i]),max(a[i],b[i])-1);
     q[idx+1].push_back(i);
    }
  t=1;
   ll ans=0;  memset(seg,0,sizeof(seg));
   for (int i=k;i>=0;i--)
	{
	    if(i!=k){ update(1,0,sz,T[i],1);}
        for (int j:q[i])
		{   int parity;
			parity=query(1,0,sz,max(a[j],b[j]),sz)%2;
		if(i==0)
    		parity ^= a[j] < b[j];
         if(parity){
            ans+=min(bb[j],aa[j]);

         }else{
          ans+=max(bb[j],aa[j]);

          }
    	//cout<<i<<" "<<j<<" "<<parity<<"\n";
    	}
    	}
    	cout<<ans;
    	}

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