제출 #1332453

#제출 시각아이디문제언어결과실행 시간메모리
1332453nathjess운세 보기 2 (JOI14_fortune_telling2)C++20
100 / 100
1236 ms109708 KiB
# include <bits/stdc++.h>
# define int long long
# define vi vector<int>
# define pb push_back
# define pii pair<int, int>
# define fi first
# define se second
# define endl '\n'
# define jess ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int n, k, a[200005], b[200005], t[200005], tree[2][4*600005], last[200005];
map<int, int> pos;
vi lst[200005];
int cur[200005];

void update(int t, int idx, int l, int r, int x, int v) {
   if(l==r) {
      if(t==0) tree[t][idx]=v;
      else tree[t][idx]+=v;
      return;
   }
   int mid=(l+r)/2;
   if(x<=mid) update(t, idx*2, l, mid, x, v);
   else update(t, idx*2+1, mid+1, r, x, v);
   if(t==0) tree[t][idx]=max(tree[t][idx*2], tree[t][idx*2+1]);
   else tree[t][idx]=tree[t][idx*2]+tree[t][idx*2+1]; 
}

int get(int t, int idx, int l, int r, int x, int y) {
   if(l>y || r<x || l>r || x>y) return 0;
   if(l>=x && r<=y) return tree[t][idx];
   int mid=(l+r)/2;
   int ql=get(t, idx*2, l, mid, x, y);
   int qr=get(t, idx*2+1, mid+1, r, x, y);
   if(t==0) return max(ql, qr);
   else return ql+qr;

}

void solve () {
   cin >> n >> k;
   set<int> s;
   for(int i=1; i<=n; i++) {
      cin >> a[i] >> b[i];
      s.insert(a[i]);
      s.insert(b[i]);
   }
   for(int i=1; i<=k; i++) {
      cin >> t[i];
      s.insert(t[i]);
   }
   int cnt=1;
   for(int i : s) pos[i]=cnt, cnt++;
   cnt--;
   for(int i=1; i<=k; i++) {
      update(0, 1, 1, cnt, pos[t[i]], i);
   }
   for(int i=1; i<=n; i++) {
      int mn1=min(a[i], b[i]), mx1=max(a[i], b[i]);
      last[i]=get(0, 1, 1, cnt, pos[mn1], pos[mx1]-1);
      if(last[i]==0) cur[i]=a[i], lst[1].pb(i);
      else cur[i]=mx1, lst[last[i]].pb(i);
   }
   for(int i=k; i>=1; i--) {
      update(1, 1, 1, cnt, pos[t[i]], 1);
      for(int j : lst[i]) {
         int mx=max(a[j], b[j]);
         int tmp=get(1, 1, 1, cnt, pos[mx], cnt);
         if(tmp%2==1) {
            if(cur[j]==a[j]) cur[j]=b[j];
            else cur[j]=a[j]; 
         }  
      }
   }
   int sum=0;
   for(int i=1; i<=n; i++) sum+=cur[i];
   cout << sum << endl;
}
 
signed main() {
   jess;
   solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...