oj.uz

Submission #295447

# Submission time Handle Problem Language Result Execution time Memory
295447 2020-09-09T16:47:13 Z limabeans Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 250 ms 7416 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 2e5+10;
const int inf = 2e9;

int n, k;
vector<array<int,2>> card;
vector<pair<int,int>> flip; // value, index


bool sum[maxn*4];
int tmin[maxn*4];

void build(int v, int tl, int tr) {
    if (tl==tr) {
	tmin[v]=inf;
    } else {
	int tm=(tl+tr)/2;
	build(2*v,tl,tm);
	build(2*v+1,tm+1,tr);
	tmin[v]=min(tmin[2*v],tmin[2*v+1]);
    }
}

void upd(int v, int tl, int tr, int i, int val) {
    if (tl==tr) {
	tmin[v] = val;
	sum[v] = true;
    } else {
	int tm=(tl+tr)/2;
	if (i<=tm) {
	    upd(2*v,tl,tm,i,val);
	} else {
	    upd(2*v+1,tm+1,tr,i,val);
	}
	tmin[v] = min(tmin[2*v], tmin[2*v+1]);
	sum[v] = sum[2*v] ^ sum[2*v+1];
    }
}


// 0: everything is >= val
// get first index from rhs that is < val
int get(int v, int tl, int tr, int val) {
    if (val <= tmin[v]) {
	return 0;
    }
    if (tl==tr) {
	assert(tmin[v]<val);
	return tl;
    } else {
	int tm=(tl+tr)/2;
	int rhs = get(2*v+1,tm+1,tr,val);
	if (rhs > 0) {
	    return rhs;
	}
	return get(2*v,tl,tm,val);
    }
}

bool qry(int v, int tl, int tr, int l, int r) {
    if (l>r) return false;
    if (l==tl && tr==r) return sum[v];
    int tm=(tl+tr)/2;
    return qry(2*v,tl,tm,l,min(r,tm)) ^ qry(2*v+1,tm+1,tr,max(tm+1,l),r);
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k;
    card.resize(n);
    for (int i=0; i<n; i++) {
	cin>>card[i][0]>>card[i][1];
    }
    flip.resize(k);
    for (int i=1; i<=k; i++) {
	cin>>flip[i-1].first;
	flip[i-1].second=i;
    }


    sort(flip.rbegin(),flip.rend());

    sort(card.begin(), card.end(), [&](array<int,2> c1, array<int,2> c2) {
	    return min(c1[0],c1[1]) > min(c2[0],c2[1]);
	});


    build(1,1,k);


    ll res = 0;
    int j=0;
    for (auto ca: card) {
	int lo = min(ca[0], ca[1]);
	int hi = max(ca[0], ca[1]);

	bool flag = false;
	if (lo == ca[0]) {
	    flag = true;
	    swap(ca[0], ca[1]);
	}

	assert(ca[0] >= ca[1]);
	
	while (j<k && flip[j].first >= lo) {
	    upd(1,1,k,flip[j].second,flip[j].first);
	    j++;
	}
	
	int p = get(1,1,k,hi);
	// p=0 if every card >= hi

	bool parity = (p==k ? false : qry(1,1,k,p+1,k));
	
	if (flag && p==0) {
	    parity=!parity;
	}
	//cout<<ca[0]<<" "<<ca[1]<<": "<<ca[parity]<<endl;
	
	res += ca[parity];
    }

    cout<<res<<endl;    
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 14 ms 896 KB Output is correct
15 Correct 22 ms 1576 KB Output is correct
16 Correct 27 ms 1792 KB Output is correct
17 Correct 38 ms 2296 KB Output is correct
18 Correct 38 ms 2304 KB Output is correct
19 Correct 48 ms 2296 KB Output is correct
20 Correct 45 ms 2384 KB Output is correct
21 Correct 36 ms 2424 KB Output is correct
22 Correct 31 ms 2296 KB Output is correct
23 Correct 31 ms 2304 KB Output is correct
24 Correct 33 ms 2304 KB Output is correct
25 Correct 29 ms 2304 KB Output is correct
26 Correct 36 ms 2280 KB Output is correct
27 Correct 42 ms 2304 KB Output is correct
28 Correct 50 ms 2296 KB Output is correct
29 Correct 39 ms 2304 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 14 ms 896 KB Output is correct
15 Correct 22 ms 1576 KB Output is correct
16 Correct 27 ms 1792 KB Output is correct
17 Correct 38 ms 2296 KB Output is correct
18 Correct 38 ms 2304 KB Output is correct
19 Correct 48 ms 2296 KB Output is correct
20 Correct 45 ms 2384 KB Output is correct
21 Correct 36 ms 2424 KB Output is correct
22 Correct 31 ms 2296 KB Output is correct
23 Correct 31 ms 2304 KB Output is correct
24 Correct 33 ms 2304 KB Output is correct
25 Correct 29 ms 2304 KB Output is correct
26 Correct 36 ms 2280 KB Output is correct
27 Correct 42 ms 2304 KB Output is correct
28 Correct 50 ms 2296 KB Output is correct
29 Correct 39 ms 2304 KB Output is correct
30 Correct 114 ms 5264 KB Output is correct
31 Correct 142 ms 5496 KB Output is correct
32 Correct 171 ms 5980 KB Output is correct
33 Correct 215 ms 6852 KB Output is correct
34 Correct 99 ms 5628 KB Output is correct
35 Correct 250 ms 7248 KB Output is correct
36 Correct 200 ms 7288 KB Output is correct
37 Correct 217 ms 7160 KB Output is correct
38 Correct 210 ms 7160 KB Output is correct
39 Correct 233 ms 7256 KB Output is correct
40 Correct 184 ms 7160 KB Output is correct
41 Correct 214 ms 7248 KB Output is correct
42 Correct 215 ms 7348 KB Output is correct
43 Correct 162 ms 7256 KB Output is correct
44 Correct 165 ms 7160 KB Output is correct
45 Correct 166 ms 7288 KB Output is correct
46 Correct 196 ms 7248 KB Output is correct
47 Correct 207 ms 7416 KB Output is correct
48 Correct 214 ms 7160 KB Output is correct
49 Correct 178 ms 7160 KB Output is correct