oj.uz

Submission #852820

# Submission time Handle Problem Language Result Execution time Memory
852820 2023-09-22T18:59:08 Z epicci23 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1643 ms 167748 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int N = 2e5 + 5;

int n,k;
array<int,2> ar[N];

struct SegT{
  vector<int> seg;
  SegT(int n){seg.assign(4*n+5,0);}

  void update(int rt,int l,int r,int ind,int u){
  	if(r<ind || l>ind) return;
  	if(l==r){
  	 seg[rt]=max(seg[rt],u);
  	 return;
  	}
  	int m=(l+r)/2;
  	update(rt*2,l,m,ind,u);update(rt*2+1,m+1,r,ind,u);
  	seg[rt]=max(seg[rt*2],seg[rt*2+1]);
  }

  int query(int rt,int l,int r,int gl,int gr){
  	if(r<gl || l>gr) return 0;
  	if(l>=gl && r<=gr) return seg[rt];
  	int m=(l+r)/2;
  	return max(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
  }
};

vector<int> seg[4*N];
int xd[N];

void build(int rt,int l,int r){
  if(l==r){
  	seg[rt].pb(xd[l]);
  	return;
  }
  int m=(l+r)/2;
  build(rt*2,l,m);build(rt*2+1,m+1,r);
  int p1=0,p2=0;
  while(p1<sz(seg[rt*2]) && p2<sz(seg[rt*2+1])){
  	if(seg[rt*2][p1] <= seg[rt*2+1][p2]) seg[rt].pb(seg[rt*2][p1++]);
  	else seg[rt].pb(seg[rt*2+1][p2++]);
  }

  while(p1<sz(seg[rt*2])) seg[rt].pb(seg[rt*2][p1++]);
  while(p2<sz(seg[rt*2+1])) seg[rt].pb(seg[rt*2+1][p2++]);
}

int query(int rt,int l,int r,int gl,int gr,int x){
   if(r<gl || l>gr || gl>gr || l>r) return 0;
   if(l>=gl && r<=gr){
   	 int lol=lower_bound(all(seg[rt]),x)-seg[rt].begin();
   	 return sz(seg[rt])-lol;
   }
   int m=(l+r)/2;
   return query(rt*2,l,m,gl,gr,x) + query(rt*2+1,m+1,r,gl,gr,x);
}

void solve(){

  cin >> n >> k;
  map<int,int> mp;
  for(int i=1;i<=n;i++){
  	int a,b;
  	cin >> a >> b;
  	ar[i]={a,b};
  	mp[a]=mp[b]=mp[a-1]=mp[b-1]=1;
  }
  
  
  for(int i=1;i<=k;i++){ 
  	cin >> xd[i];
  	mp[xd[i]]=1;
  }
  
  int p=0;
  for(auto x:mp) mp[x.first]=++p;
  
  SegT Seg(p);

  for(int i=1;i<=k;i++) Seg.update(1,1,p,mp[xd[i]],i);

  build(1,1,k);
  
  int ans=0;

  for(int i=1;i<=n;i++){
    if(ar[i][0]==ar[i][1]){
      ans+=ar[i][0];
      continue;
    }
    bool ok=0;
    if(ar[i][0]>ar[i][1]){
       swap(ar[i][0],ar[i][1]);
       ok=1;
    }
    int hm=Seg.query(1,1,p,mp[ar[i][0]],mp[ar[i][1]-1]);
    int f=query(1,1,k,hm+1,k,ar[i][1]);
    if(hm) ok=1;
    //cout << i << ": " << hm << " " << f << endl;
    if(!ok){
      if(f&1) ans+=ar[i][1];
      else ans+=ar[i][0];
    }
    else{
      if(f&1) ans+=ar[i][0];
      else ans+=ar[i][1];
    }
  }

  cout << ans << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 6 ms 21260 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 6 ms 21596 KB Output is correct
5 Correct 6 ms 21596 KB Output is correct
6 Correct 6 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 6 ms 21508 KB Output is correct
9 Correct 6 ms 21336 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 6 ms 21340 KB Output is correct
12 Correct 6 ms 21260 KB Output is correct
13 Correct 6 ms 21340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 6 ms 21260 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 6 ms 21596 KB Output is correct
5 Correct 6 ms 21596 KB Output is correct
6 Correct 6 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 6 ms 21508 KB Output is correct
9 Correct 6 ms 21336 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 6 ms 21340 KB Output is correct
12 Correct 6 ms 21260 KB Output is correct
13 Correct 6 ms 21340 KB Output is correct
14 Correct 35 ms 27992 KB Output is correct
15 Correct 71 ms 35408 KB Output is correct
16 Correct 112 ms 43348 KB Output is correct
17 Correct 164 ms 51920 KB Output is correct
18 Correct 171 ms 51964 KB Output is correct
19 Correct 171 ms 51920 KB Output is correct
20 Correct 177 ms 52300 KB Output is correct
21 Correct 158 ms 51924 KB Output is correct
22 Correct 94 ms 40400 KB Output is correct
23 Correct 86 ms 38348 KB Output is correct
24 Correct 86 ms 37104 KB Output is correct
25 Correct 98 ms 41420 KB Output is correct
26 Correct 97 ms 43364 KB Output is correct
27 Correct 123 ms 44616 KB Output is correct
28 Correct 116 ms 44496 KB Output is correct
29 Correct 144 ms 48336 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 6 ms 21260 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 6 ms 21596 KB Output is correct
5 Correct 6 ms 21596 KB Output is correct
6 Correct 6 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 6 ms 21508 KB Output is correct
9 Correct 6 ms 21336 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 6 ms 21340 KB Output is correct
12 Correct 6 ms 21260 KB Output is correct
13 Correct 6 ms 21340 KB Output is correct
14 Correct 35 ms 27992 KB Output is correct
15 Correct 71 ms 35408 KB Output is correct
16 Correct 112 ms 43348 KB Output is correct
17 Correct 164 ms 51920 KB Output is correct
18 Correct 171 ms 51964 KB Output is correct
19 Correct 171 ms 51920 KB Output is correct
20 Correct 177 ms 52300 KB Output is correct
21 Correct 158 ms 51924 KB Output is correct
22 Correct 94 ms 40400 KB Output is correct
23 Correct 86 ms 38348 KB Output is correct
24 Correct 86 ms 37104 KB Output is correct
25 Correct 98 ms 41420 KB Output is correct
26 Correct 97 ms 43364 KB Output is correct
27 Correct 123 ms 44616 KB Output is correct
28 Correct 116 ms 44496 KB Output is correct
29 Correct 144 ms 48336 KB Output is correct
30 Correct 341 ms 89628 KB Output is correct
31 Correct 633 ms 107756 KB Output is correct
32 Correct 949 ms 127544 KB Output is correct
33 Correct 1628 ms 167544 KB Output is correct
34 Correct 291 ms 85760 KB Output is correct
35 Correct 1605 ms 167556 KB Output is correct
36 Correct 1611 ms 167432 KB Output is correct
37 Correct 1640 ms 167468 KB Output is correct
38 Correct 1557 ms 167624 KB Output is correct
39 Correct 1631 ms 167540 KB Output is correct
40 Correct 1351 ms 167092 KB Output is correct
41 Correct 1580 ms 167748 KB Output is correct
42 Correct 1643 ms 167608 KB Output is correct
43 Correct 653 ms 129480 KB Output is correct
44 Correct 636 ms 129276 KB Output is correct
45 Correct 637 ms 129156 KB Output is correct
46 Correct 598 ms 99780 KB Output is correct
47 Correct 493 ms 90616 KB Output is correct
48 Correct 887 ms 129952 KB Output is correct
49 Correct 850 ms 129968 KB Output is correct