oj.uz

Submission #937756

# Submission time Handle Problem Language Result Execution time Memory
937756 2024-03-04T12:37:46 Z KiaRez Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 339 ms 59988 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 1e6+1e5+23, lg = 20;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, k, a[N], b[N], ans[N], seg[2*N], t[N], fen[N];
vector<int> comp, Q[N];

int get(int val) {
	int ptr = lower_bound(all(comp), val) - comp.begin() + 1;
	return ptr;
}

void upd(int ind, int val) {
	if(ind == 0) return ;
	if(ind >= (1<<lg)) seg[ind] = val;
	else seg[ind] = max(seg[2*ind], seg[2*ind+1]);
	upd(ind/2, val);
}

int query(int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
	if(l>=rc || lc>=r) return 0;
	if(lc>=l && rc<=r) return seg[ind];
	int mid = (lc+rc)/2;
	return max(query(l, r, 2*ind, lc, mid), query(l, r, 2*ind+1, mid, rc));
}

void add(int ind, int val) {
	while(ind < N) {
		fen[ind] += val; ind += (ind&(-ind));
	}
}
int qry(int ind) {
	int res=0; while(ind>0) {res+=fen[ind]; ind-=(ind&(-ind));} return res;
}

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

	cin>>n>>k;
	for(int i=1; i<=n; i++) {
		cin>>a[i]>>b[i];
		comp.pb(a[i]); comp.pb(b[i]);
	}
	for(int i=1; i<=k; i++) {
		cin>>t[i]; comp.pb(t[i]);
	}

	comp.pb(1e9+1);
	sort(all(comp));
	comp.resize(unique(all(comp)) - comp.begin());

	for(int i=1; i<=k; i++) {
		upd(get(t[i])+(1<<lg)-1, i);
	}
	for(int i=1; i<=n; i++) {
		int l=get(a[i]), r=get(b[i]);
		if(l>r) swap(l,r);
		Q[query(l, r)].pb(i);
	}
	for(int i=k; i>=0; i--) {
		for(auto it : Q[i]) {
			int f = qry(N-1) - qry(get(max(a[it],b[it]))-1);
			if(i>0 && a[it]<b[it]) f++;
			if(f%2==1) ans[it] = b[it];
			else ans[it] = a[it];
		}
		add(get(t[i]), 1);
	}

	ll answ = 0;
	for(int i=1; i<=n; i++) answ += ((ll)ans[i]);
	cout<<answ<<endl;

	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43608 KB Output is correct
2 Correct 10 ms 43868 KB Output is correct
3 Correct 10 ms 43612 KB Output is correct
4 Correct 9 ms 43704 KB Output is correct
5 Correct 9 ms 43612 KB Output is correct
6 Correct 9 ms 43612 KB Output is correct
7 Correct 10 ms 43708 KB Output is correct
8 Correct 9 ms 43612 KB Output is correct
9 Correct 10 ms 43776 KB Output is correct
10 Correct 9 ms 43712 KB Output is correct
11 Correct 9 ms 43608 KB Output is correct
12 Correct 10 ms 43656 KB Output is correct
13 Correct 10 ms 43608 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43608 KB Output is correct
2 Correct 10 ms 43868 KB Output is correct
3 Correct 10 ms 43612 KB Output is correct
4 Correct 9 ms 43704 KB Output is correct
5 Correct 9 ms 43612 KB Output is correct
6 Correct 9 ms 43612 KB Output is correct
7 Correct 10 ms 43708 KB Output is correct
8 Correct 9 ms 43612 KB Output is correct
9 Correct 10 ms 43776 KB Output is correct
10 Correct 9 ms 43712 KB Output is correct
11 Correct 9 ms 43608 KB Output is correct
12 Correct 10 ms 43656 KB Output is correct
13 Correct 10 ms 43608 KB Output is correct
14 Correct 20 ms 46168 KB Output is correct
15 Correct 34 ms 46684 KB Output is correct
16 Correct 55 ms 47132 KB Output is correct
17 Correct 63 ms 47572 KB Output is correct
18 Correct 65 ms 47572 KB Output is correct
19 Correct 63 ms 47572 KB Output is correct
20 Correct 67 ms 47516 KB Output is correct
21 Correct 63 ms 47568 KB Output is correct
22 Correct 50 ms 47064 KB Output is correct
23 Correct 50 ms 47068 KB Output is correct
24 Correct 48 ms 47084 KB Output is correct
25 Correct 50 ms 47200 KB Output is correct
26 Correct 52 ms 47360 KB Output is correct
27 Correct 60 ms 47528 KB Output is correct
28 Correct 51 ms 47540 KB Output is correct
29 Correct 59 ms 47572 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43608 KB Output is correct
2 Correct 10 ms 43868 KB Output is correct
3 Correct 10 ms 43612 KB Output is correct
4 Correct 9 ms 43704 KB Output is correct
5 Correct 9 ms 43612 KB Output is correct
6 Correct 9 ms 43612 KB Output is correct
7 Correct 10 ms 43708 KB Output is correct
8 Correct 9 ms 43612 KB Output is correct
9 Correct 10 ms 43776 KB Output is correct
10 Correct 9 ms 43712 KB Output is correct
11 Correct 9 ms 43608 KB Output is correct
12 Correct 10 ms 43656 KB Output is correct
13 Correct 10 ms 43608 KB Output is correct
14 Correct 20 ms 46168 KB Output is correct
15 Correct 34 ms 46684 KB Output is correct
16 Correct 55 ms 47132 KB Output is correct
17 Correct 63 ms 47572 KB Output is correct
18 Correct 65 ms 47572 KB Output is correct
19 Correct 63 ms 47572 KB Output is correct
20 Correct 67 ms 47516 KB Output is correct
21 Correct 63 ms 47568 KB Output is correct
22 Correct 50 ms 47064 KB Output is correct
23 Correct 50 ms 47068 KB Output is correct
24 Correct 48 ms 47084 KB Output is correct
25 Correct 50 ms 47200 KB Output is correct
26 Correct 52 ms 47360 KB Output is correct
27 Correct 60 ms 47528 KB Output is correct
28 Correct 51 ms 47540 KB Output is correct
29 Correct 59 ms 47572 KB Output is correct
30 Correct 115 ms 51400 KB Output is correct
31 Correct 157 ms 50368 KB Output is correct
32 Correct 219 ms 54396 KB Output is correct
33 Correct 338 ms 59004 KB Output is correct
34 Correct 102 ms 48864 KB Output is correct
35 Correct 320 ms 58516 KB Output is correct
36 Correct 328 ms 58300 KB Output is correct
37 Correct 323 ms 58440 KB Output is correct
38 Correct 339 ms 58744 KB Output is correct
39 Correct 317 ms 59328 KB Output is correct
40 Correct 334 ms 59148 KB Output is correct
41 Correct 324 ms 58304 KB Output is correct
42 Correct 328 ms 59948 KB Output is correct
43 Correct 253 ms 57788 KB Output is correct
44 Correct 237 ms 59988 KB Output is correct
45 Correct 233 ms 59140 KB Output is correct
46 Correct 236 ms 58556 KB Output is correct
47 Correct 218 ms 57924 KB Output is correct
48 Correct 261 ms 59796 KB Output is correct
49 Correct 259 ms 59952 KB Output is correct