oj.uz

Submission #505753

# Submission time Handle Problem Language Result Execution time Memory
505753 2022-01-11T07:33:03 Z Abrar_Al_Samit Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 2561 ms 262148 KB 
#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
const int uMX = 600006;

int n, k;
int a[MX], b[MX];
int ops[MX];
map<int,int>HASH;
set<int>store[uMX*4];

void enlist(int l, int r, int L, int R, int id, int v) {
  if(l>=L && r<=R) {
    store[v].insert(id);
    return;
  }
  if(l>R || r<L) return;
  int m = (l+r)/2;
  enlist(l, m, L, R, id, v*2);
  enlist(m+1, r, L, R, id, v*2+1);
}
void delist(int l, int r, int L, int R, int id, int v) {
  if(l>=L && r<=R) {
    store[v].erase(id);
    return;
  }
  if(l>R || r<L) return;
  int m = (l+r)/2;
  delist(l, m, L, R, id, v*2);
  delist(m+1, r, L, R, id, v*2+1);
}
vector<int>st(uMX*4);
void upd(int l, int r, int dest, int v) {
  if(l==r) {
    ++st[v];
    return;
  }
  int m = (l+r)/2;
  if(dest<=m) upd(l, m, dest, v*2);
  else upd(m+1, r, dest, v*2+1);
  st[v] = st[v*2]+st[v*2+1];
}
int getCount(int l, int r, int L, int R, int v) {
  if(l>=L && r<=R) {
    return st[v];
  } 
  if(l>R || r<L) return 0;
  int m = (l+r)/2;
  return getCount(l, m, L, R, v*2) + getCount(m+1, r, L, R, v*2+1);
}
set<int>get(int l, int r, int p, int v) {
  set<int>ret = store[v];
  if(l==r) return ret;
  int m = (l+r)/2;
  set<int>got;
  if(p<=m) {
    got = get(l, m, p, v*2);
  } else {
    got = get(m+1, r, p, v*2+1);
  }
  while(!got.empty()) {
    ret.insert(*got.begin());
    got.erase(got.begin());
  }
  return ret;
}
void PlayGround() {
  cin >> n >> k;
  for(int i=1; i<=n; ++i) {
    cin >> a[i] >> b[i];
    HASH[a[i]] = HASH[b[i]] = 0;
  }
  for(int i=1; i<=k; ++i) {
    cin >> ops[i];
    HASH[ops[i]] = i;
  }
  int tag = 1;
  for(auto &p : HASH) {
    p.second = tag++;
  } //end of HASH stuffs


  long long ans = 0;
  set<int>done;
  for(int i=1; i<=n; ++i) {
    if(a[i]==b[i]) {
      done.insert(i);
      ans += a[i];
      continue;
    }
    int mn = a[i], mx = b[i];
    if(mn>mx) swap(mn, mx);
    enlist(1, uMX-1, HASH[mn], HASH[mx]-1, i, 1);
  }
  for(int i=k; i>0; --i) {
    set<int>cur = get(1, uMX-1, HASH[ops[i]], 1);
    for(int j : cur) {
      int mn = a[j], mx = b[j];
      if(mn>mx) swap(mn, mx);
      delist(1, uMX-1, HASH[mn], HASH[mx]-1, j, 1);
      done.insert(j);
      int cnt = getCount(1, uMX-1, HASH[mx], uMX-1, 1);
      ans += (cnt&1)?mn:mx;
    }
    upd(1, uMX-1, HASH[ops[i]], 1);
  }

  for(int i=1; i<=n; ++i) if(!done.count(i)) {
    int mn = a[i], mx = b[i];
    if(mn>mx) swap(mn, mx);
    int cnt = getCount(1, uMX-1, HASH[mx], uMX-1, 1);
    ans += (~cnt&1)?a[i]:b[i];
  }
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 122548 KB Output is correct
2 Correct 57 ms 122692 KB Output is correct
3 Correct 57 ms 122968 KB Output is correct
4 Correct 64 ms 122980 KB Output is correct
5 Correct 61 ms 122948 KB Output is correct
6 Correct 64 ms 123116 KB Output is correct
7 Correct 55 ms 122816 KB Output is correct
8 Correct 59 ms 123076 KB Output is correct
9 Correct 57 ms 123100 KB Output is correct
10 Correct 57 ms 122792 KB Output is correct
11 Correct 73 ms 122784 KB Output is correct
12 Correct 56 ms 122820 KB Output is correct
13 Correct 55 ms 122688 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 122548 KB Output is correct
2 Correct 57 ms 122692 KB Output is correct
3 Correct 57 ms 122968 KB Output is correct
4 Correct 64 ms 122980 KB Output is correct
5 Correct 61 ms 122948 KB Output is correct
6 Correct 64 ms 123116 KB Output is correct
7 Correct 55 ms 122816 KB Output is correct
8 Correct 59 ms 123076 KB Output is correct
9 Correct 57 ms 123100 KB Output is correct
10 Correct 57 ms 122792 KB Output is correct
11 Correct 73 ms 122784 KB Output is correct
12 Correct 56 ms 122820 KB Output is correct
13 Correct 55 ms 122688 KB Output is correct
14 Correct 144 ms 130456 KB Output is correct
15 Correct 290 ms 139472 KB Output is correct
16 Correct 477 ms 148824 KB Output is correct
17 Correct 664 ms 158108 KB Output is correct
18 Correct 737 ms 158404 KB Output is correct
19 Correct 681 ms 159956 KB Output is correct
20 Correct 553 ms 152596 KB Output is correct
21 Correct 603 ms 161988 KB Output is correct
22 Correct 374 ms 157452 KB Output is correct
23 Correct 352 ms 154316 KB Output is correct
24 Correct 305 ms 148924 KB Output is correct
25 Correct 349 ms 159360 KB Output is correct
26 Correct 372 ms 143940 KB Output is correct
27 Correct 377 ms 142604 KB Output is correct
28 Correct 399 ms 146272 KB Output is correct
29 Correct 241 ms 131716 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 122548 KB Output is correct
2 Correct 57 ms 122692 KB Output is correct
3 Correct 57 ms 122968 KB Output is correct
4 Correct 64 ms 122980 KB Output is correct
5 Correct 61 ms 122948 KB Output is correct
6 Correct 64 ms 123116 KB Output is correct
7 Correct 55 ms 122816 KB Output is correct
8 Correct 59 ms 123076 KB Output is correct
9 Correct 57 ms 123100 KB Output is correct
10 Correct 57 ms 122792 KB Output is correct
11 Correct 73 ms 122784 KB Output is correct
12 Correct 56 ms 122820 KB Output is correct
13 Correct 55 ms 122688 KB Output is correct
14 Correct 144 ms 130456 KB Output is correct
15 Correct 290 ms 139472 KB Output is correct
16 Correct 477 ms 148824 KB Output is correct
17 Correct 664 ms 158108 KB Output is correct
18 Correct 737 ms 158404 KB Output is correct
19 Correct 681 ms 159956 KB Output is correct
20 Correct 553 ms 152596 KB Output is correct
21 Correct 603 ms 161988 KB Output is correct
22 Correct 374 ms 157452 KB Output is correct
23 Correct 352 ms 154316 KB Output is correct
24 Correct 305 ms 148924 KB Output is correct
25 Correct 349 ms 159360 KB Output is correct
26 Correct 372 ms 143940 KB Output is correct
27 Correct 377 ms 142604 KB Output is correct
28 Correct 399 ms 146272 KB Output is correct
29 Correct 241 ms 131716 KB Output is correct
30 Correct 599 ms 143360 KB Output is correct
31 Correct 1384 ms 179780 KB Output is correct
32 Correct 2561 ms 226620 KB Output is correct
33 Runtime error 2009 ms 262148 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -