oj.uz

Submission #535929

# Submission time Handle Problem Language Result Execution time Memory
535929 2022-03-11T21:28:52 Z michao Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1455 ms 87692 KB 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
const int MAX=6e5+5;
const int inf=(int)1e9+9;
int l[MAX],r[MAX],c[MAX];
map<int,int>compress;
set<int>pom;
int tl[MAX],tr[MAX];
int t[MAX*2];
void update(int u,int ce){
  u+=MAX;
	for (t[u]=max(t[u],ce);u>1;u>>=1){
		t[u>>1]=max(t[u],t[u^1]);
	}
}

int query(int u,int v){
	int maxi=-inf;
	for (u+=MAX,v+=MAX+1;u<v;u>>=1,v>>=1){
		if (u&1)maxi=max(maxi,t[u++]);
		if (v&1)maxi=max(maxi,t[--v]);
	}
	return maxi;
}

int start[MAX];
vector<pii>rak;

int para[MAX],dara[MAX];

inline void readUI(int *n) //tylko dodatnie
{
    register char c = 0;
    while (c < 33) c=getc_unlocked(stdin);
    (*n) = 0;
    while (c>32) {(*n)=(*n)*10LL + (c-48); c=getc_unlocked(stdin);}
}

ordered_set secik;
int32_t main(){
  //BOOST;
  
  for (int i=0;i<2*MAX;i++)t[i]=-inf;
  int n,k;
  readUI(&n);
  readUI(&k);
  for (int i=1;i<=n;i++){
		readUI(&l[i]);
		readUI(&r[i]);
  }
  
  for (int i=1;i<=n;i++){
		para[i]=l[i];
		dara[i]=r[i];
  }
  
  for (int i=1;i<=n;i++){
		if (l[i]>r[i])swap(l[i],r[i]);
  }
  
  for (int i=1;i<=n;i++){
		tl[i]=l[i];
		tr[i]=r[i]-1;
		if (l[i]==r[i])continue;
		pom.ins(tl[i]);
		pom.ins(tr[i]);
  }	
  for (int i=1;i<=k;i++)readUI(&c[i]),pom.ins(c[i]);
  int licznik=1;
  for (auto it:pom){
		compress[it]=licznik++;
  }
  
  for (int i=1;i<=k;i++){
		update(compress[c[i]],i);
  }
  ll ans=0;
  for (int i=1;i<=n;i++){
		if (l[i]==r[i])ans+=l[i];
		else{
			start[i]=query(compress[tl[i]],compress[tr[i]])+1;
			rak.pb(mp(start[i],i));
		}
  }	
  sort(rak.begin(),rak.end());
 // ll ans=0;
  int akt=k;
  int cnt=0;
  while (!rak.empty()){
		pii kot=rak.back();
		rak.pop_back();
		int id=kot.nd;
		int doilu=kot.st;
		while (akt>=doilu && akt>=1){
		  secik.ins(mp(c[akt],cnt++)); 
			akt--;
		}
		
		int wykonuje=sz(secik)-(int)secik.order_of_key(mp(l[id],-inf));
		if (doilu<0){
			if (wykonuje&1)ans+=dara[id];
			else ans+=para[id];
		}
		else{
			if (wykonuje&1)ans+=l[id];
			else ans+=r[id];
		}
  }
  printf("%lld",ans);
  return 0;   
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5304 KB Output is correct
3 Correct 4 ms 5340 KB Output is correct
4 Correct 5 ms 5428 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 6 ms 5404 KB Output is correct
7 Correct 7 ms 5468 KB Output is correct
8 Correct 6 ms 5420 KB Output is correct
9 Correct 6 ms 5332 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 4 ms 5332 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5304 KB Output is correct
3 Correct 4 ms 5340 KB Output is correct
4 Correct 5 ms 5428 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 6 ms 5404 KB Output is correct
7 Correct 7 ms 5468 KB Output is correct
8 Correct 6 ms 5420 KB Output is correct
9 Correct 6 ms 5332 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 4 ms 5332 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 25 ms 9068 KB Output is correct
15 Correct 53 ms 12936 KB Output is correct
16 Correct 94 ms 17416 KB Output is correct
17 Correct 180 ms 21080 KB Output is correct
18 Correct 147 ms 21512 KB Output is correct
19 Correct 127 ms 19344 KB Output is correct
20 Correct 164 ms 21520 KB Output is correct
21 Correct 137 ms 19272 KB Output is correct
22 Correct 68 ms 15032 KB Output is correct
23 Correct 56 ms 13152 KB Output is correct
24 Correct 55 ms 11816 KB Output is correct
25 Correct 84 ms 16168 KB Output is correct
26 Correct 89 ms 16720 KB Output is correct
27 Correct 100 ms 17824 KB Output is correct
28 Correct 90 ms 17168 KB Output is correct
29 Correct 135 ms 19632 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5304 KB Output is correct
3 Correct 4 ms 5340 KB Output is correct
4 Correct 5 ms 5428 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 6 ms 5404 KB Output is correct
7 Correct 7 ms 5468 KB Output is correct
8 Correct 6 ms 5420 KB Output is correct
9 Correct 6 ms 5332 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 4 ms 5332 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 25 ms 9068 KB Output is correct
15 Correct 53 ms 12936 KB Output is correct
16 Correct 94 ms 17416 KB Output is correct
17 Correct 180 ms 21080 KB Output is correct
18 Correct 147 ms 21512 KB Output is correct
19 Correct 127 ms 19344 KB Output is correct
20 Correct 164 ms 21520 KB Output is correct
21 Correct 137 ms 19272 KB Output is correct
22 Correct 68 ms 15032 KB Output is correct
23 Correct 56 ms 13152 KB Output is correct
24 Correct 55 ms 11816 KB Output is correct
25 Correct 84 ms 16168 KB Output is correct
26 Correct 89 ms 16720 KB Output is correct
27 Correct 100 ms 17824 KB Output is correct
28 Correct 90 ms 17168 KB Output is correct
29 Correct 135 ms 19632 KB Output is correct
30 Correct 297 ms 29492 KB Output is correct
31 Correct 648 ms 51120 KB Output is correct
32 Correct 920 ms 63328 KB Output is correct
33 Correct 1391 ms 86692 KB Output is correct
34 Correct 317 ms 26436 KB Output is correct
35 Correct 1433 ms 87472 KB Output is correct
36 Correct 1391 ms 87648 KB Output is correct
37 Correct 1455 ms 87524 KB Output is correct
38 Correct 1388 ms 75352 KB Output is correct
39 Correct 1450 ms 87692 KB Output is correct
40 Correct 1091 ms 75080 KB Output is correct
41 Correct 1232 ms 75380 KB Output is correct
42 Correct 1327 ms 75304 KB Output is correct
43 Correct 597 ms 74700 KB Output is correct
44 Correct 534 ms 74704 KB Output is correct
45 Correct 549 ms 74504 KB Output is correct
46 Correct 497 ms 45296 KB Output is correct
47 Correct 418 ms 36504 KB Output is correct
48 Correct 815 ms 68880 KB Output is correct
49 Correct 783 ms 68760 KB Output is correct