oj.uz

Submission #295449

# Submission time Handle Problem Language Result Execution time Memory
295449 2020-09-09T16:52:08 Z limabeans Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 226 ms 6196 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;
}


// Assume A[i]>=B[i]
// Insert all updates >= B[i] into segment tree.
// Find first index p from rhs s.t. updates p+1...k all affect A[i].
// This means that after index p, our card will always be flipping.
// Right when after index p, it's guaranteed that A[i] will be facing up.
// If A[i] is face up at index p, then p will not affect A[i].
// If B[i] is face up at index p, index p will flip the card!

// If A[i]<B[i]
// We flip the card initially and look for index p with B[i].
// If index p exists, it reduces to above logic.
// If p doesn't exist, every update will flip the card, and so we invert the result.

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 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 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 1 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 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 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 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 9 ms 640 KB Output is correct
15 Correct 17 ms 1024 KB Output is correct
16 Correct 26 ms 1152 KB Output is correct
17 Correct 40 ms 1656 KB Output is correct
18 Correct 36 ms 1656 KB Output is correct
19 Correct 36 ms 1692 KB Output is correct
20 Correct 38 ms 1656 KB Output is correct
21 Correct 34 ms 1664 KB Output is correct
22 Correct 29 ms 1664 KB Output is correct
23 Correct 30 ms 1664 KB Output is correct
24 Correct 32 ms 1664 KB Output is correct
25 Correct 29 ms 1664 KB Output is correct
26 Correct 32 ms 1528 KB Output is correct
27 Correct 37 ms 1656 KB Output is correct
28 Correct 37 ms 1656 KB Output is correct
29 Correct 35 ms 1664 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 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 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 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 9 ms 640 KB Output is correct
15 Correct 17 ms 1024 KB Output is correct
16 Correct 26 ms 1152 KB Output is correct
17 Correct 40 ms 1656 KB Output is correct
18 Correct 36 ms 1656 KB Output is correct
19 Correct 36 ms 1692 KB Output is correct
20 Correct 38 ms 1656 KB Output is correct
21 Correct 34 ms 1664 KB Output is correct
22 Correct 29 ms 1664 KB Output is correct
23 Correct 30 ms 1664 KB Output is correct
24 Correct 32 ms 1664 KB Output is correct
25 Correct 29 ms 1664 KB Output is correct
26 Correct 32 ms 1528 KB Output is correct
27 Correct 37 ms 1656 KB Output is correct
28 Correct 37 ms 1656 KB Output is correct
29 Correct 35 ms 1664 KB Output is correct
30 Correct 116 ms 4600 KB Output is correct
31 Correct 130 ms 4856 KB Output is correct
32 Correct 154 ms 5240 KB Output is correct
33 Correct 199 ms 6136 KB Output is correct
34 Correct 95 ms 4476 KB Output is correct
35 Correct 205 ms 6008 KB Output is correct
36 Correct 202 ms 6008 KB Output is correct
37 Correct 218 ms 6136 KB Output is correct
38 Correct 221 ms 6008 KB Output is correct
39 Correct 216 ms 6008 KB Output is correct
40 Correct 193 ms 6136 KB Output is correct
41 Correct 226 ms 6088 KB Output is correct
42 Correct 222 ms 6088 KB Output is correct
43 Correct 175 ms 6196 KB Output is correct
44 Correct 172 ms 5984 KB Output is correct
45 Correct 165 ms 6012 KB Output is correct
46 Correct 180 ms 6096 KB Output is correct
47 Correct 205 ms 6136 KB Output is correct
48 Correct 203 ms 6092 KB Output is correct
49 Correct 179 ms 6096 KB Output is correct