oj.uz

Submission #519283

# Submission time Handle Problem Language Result Execution time Memory
519283 2022-01-26T07:12:10 Z amunduzbaev Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 3000 ms 5700 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 2e5 + 5;
int a[N], b[N], f[N], t[N];
struct ST{
	int tree[N<<2], sum[N<<2];
	
	void init(){
		memset(tree, 127, sizeof tree);
	}
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = v, sum[x] = 1; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
		sum[x] = sum[x<<1] + sum[x<<1|1];
	}
	
	int get(int a, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return lx;
		int m = (lx + rx) >> 1;
		if(tree[x<<1] < a) return get(a, m+1, rx, x<<1|1);
		return get(a, lx, m, x<<1);
	}
	
	int get_s(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return sum[x];
		int m = (lx + rx) >> 1;
		return get_s(l, r, lx, m, x<<1) + get_s(l, r, m+1, rx, x<<1|1);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	tree.init();
	int n, k; cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
		if(a[i] > b[i]) f[i] = 1, swap(a[i], b[i]);
	}
	
	for(int i=0;i<k;i++){
		cin>>t[i];
	}
	
	vector<int> p(n); iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j) { return (a[i] > a[j]); });
	vector<int> q(k); iota(q.begin(), q.end(), 0);
	sort(q.begin(), q.end(), [&](int i, int j) { return (t[i] > t[j]); });
	int j = 0;
	long long res = 0;
	for(auto i : p){
		//~ while(j<k && t[q[j]] >= a[i]){
			//~ tree.sett(q[j], t[q[j]]);
			//~ j++;
		//~ }
		
		//~ int p = tree.get(b[i]);
		int s = 0, p;
		for(p=k-1;~p;p--){
			if(t[p] >= b[i]) s++;
			if(a[i] <= t[p] && t[p] < b[i]){
				break;
			}
		}
		
		if(~p && a[i] <= t[p] && t[p] < b[i]){
			//~ int s = tree.get_s(p + 1, N);
			if(s&1) res += a[i];
			else res += b[i];
		} else {
			if(f[i]) swap(a[i], b[i]);
			if(s&1) res += b[i];
			else res += a[i];
		}
	}
	
	cout<<res<<"\n";
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:57:6: warning: unused variable 'j' [-Wunused-variable]
   57 |  int j = 0;
      |      ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3532 KB Output is correct
4 Correct 2 ms 3496 KB Output is correct
5 Correct 2 ms 3532 KB Output is correct
6 Correct 2 ms 3456 KB Output is correct
7 Correct 3 ms 3532 KB Output is correct
8 Correct 2 ms 3460 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3460 KB Output is correct
11 Correct 3 ms 3460 KB Output is correct
12 Correct 3 ms 3444 KB Output is correct
13 Correct 3 ms 3484 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3532 KB Output is correct
4 Correct 2 ms 3496 KB Output is correct
5 Correct 2 ms 3532 KB Output is correct
6 Correct 2 ms 3456 KB Output is correct
7 Correct 3 ms 3532 KB Output is correct
8 Correct 2 ms 3460 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3460 KB Output is correct
11 Correct 3 ms 3460 KB Output is correct
12 Correct 3 ms 3444 KB Output is correct
13 Correct 3 ms 3484 KB Output is correct
14 Correct 7 ms 3916 KB Output is correct
15 Correct 13 ms 4420 KB Output is correct
16 Correct 17 ms 4916 KB Output is correct
17 Correct 20 ms 5500 KB Output is correct
18 Correct 21 ms 5580 KB Output is correct
19 Correct 19 ms 5496 KB Output is correct
20 Correct 28 ms 5700 KB Output is correct
21 Correct 23 ms 5444 KB Output is correct
22 Correct 14 ms 4932 KB Output is correct
23 Correct 15 ms 4868 KB Output is correct
24 Correct 14 ms 4864 KB Output is correct
25 Correct 15 ms 4872 KB Output is correct
26 Correct 1442 ms 5244 KB Output is correct
27 Correct 1833 ms 5580 KB Output is correct
28 Correct 1461 ms 5596 KB Output is correct
29 Execution timed out 3054 ms 5560 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3532 KB Output is correct
4 Correct 2 ms 3496 KB Output is correct
5 Correct 2 ms 3532 KB Output is correct
6 Correct 2 ms 3456 KB Output is correct
7 Correct 3 ms 3532 KB Output is correct
8 Correct 2 ms 3460 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3460 KB Output is correct
11 Correct 3 ms 3460 KB Output is correct
12 Correct 3 ms 3444 KB Output is correct
13 Correct 3 ms 3484 KB Output is correct
14 Correct 7 ms 3916 KB Output is correct
15 Correct 13 ms 4420 KB Output is correct
16 Correct 17 ms 4916 KB Output is correct
17 Correct 20 ms 5500 KB Output is correct
18 Correct 21 ms 5580 KB Output is correct
19 Correct 19 ms 5496 KB Output is correct
20 Correct 28 ms 5700 KB Output is correct
21 Correct 23 ms 5444 KB Output is correct
22 Correct 14 ms 4932 KB Output is correct
23 Correct 15 ms 4868 KB Output is correct
24 Correct 14 ms 4864 KB Output is correct
25 Correct 15 ms 4872 KB Output is correct
26 Correct 1442 ms 5244 KB Output is correct
27 Correct 1833 ms 5580 KB Output is correct
28 Correct 1461 ms 5596 KB Output is correct
29 Execution timed out 3054 ms 5560 KB Time limit exceeded
30 Halted 0 ms 0 KB -