oj.uz

Submission #940394

# Submission time Handle Problem Language Result Execution time Memory
940394 2024-03-07T08:51:06 Z Amirreza_Fakhri Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 286 ms 47524 KB 
// In the name of the God
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e5+5;

int n, k, a[maxn], b[maxn], t[maxn], mx[maxn*4];
vector <pii> v1, v2;
vector <int> fen[maxn];

void build1() {
    for (int i = 0; i < k; i++) {
        for (int j = k-i; j <= k; j += j&(-j)) fen[j-1].pb(v1[i].S);
    }
    for (int i = 0; i < k; i++) sort(all(fen[i]));
}

void build2(int l = 0, int r = k, int id = 1) {
    if (l+1 == r) {
        mx[id] = v2[l].S; return;
    }
    int mid = (l+r)/2;
    build2(l, mid, id*2), build2(mid, r, id*2+1);
    mx[id] = max(mx[id*2], mx[id*2+1]);
}

int get1(int i, int j) {
    int ans = 0;
    for (i = k-i; i; i &= i-1) {
        int p = lower_bound(all(fen[i-1]), j)-fen[i-1].begin();
        ans += fen[i-1].size()-p;
    }
    return ans;
}

int get2(int s, int e, int l = 0, int r = k, int id = 1) {
    if (s <= l and r <= e) return mx[id];
    int mid = (l+r)/2;
    if (e <= mid) return get2(s, e, l, mid, id*2);
    if (s >= mid) return get2(s, e, mid, r, id*2+1);
    return max(get2(s, e, l, mid, id*2), get2(s, e, mid, r, id*2+1));
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    for (int i = 0; i < k; i++) {
        cin >> t[i];
        v1.pb(mp(i, t[i]));
        v2.pb(mp(t[i], i));
    }
    sort(all(v2));
    build1(), build2();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) ans += a[i];
        else if (a[i] < b[i]) {
            bool s = 0;
            int j = lower_bound(all(v2), mp(a[i], 0ll))-v2.begin();
            int k = lower_bound(all(v2), mp(b[i], 0ll))-v2.begin();
            int time = -1;
            if (j < k) {
                s = 1;
                time = get2(j, k);
            }
            s ^= get1(time+1, b[i])&1;
            if (s) ans += b[i];
            else ans += a[i];
            // cout << i << ' ' << s << '\n';
        }
        else {
            bool s = 0;
            int j = lower_bound(all(v2), mp(b[i], 0ll))-v2.begin();
            int k = lower_bound(all(v2), mp(a[i], 0ll))-v2.begin();
            int time = -1;
            if (j < k) time = get2(j, k);
            s ^= get1(time+1, a[i])&1;
            if (s) ans += b[i];
            else ans += a[i];
            // cout << i << ' ' << s << '\n';
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10840 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10840 KB Output is correct
14 Correct 12 ms 12248 KB Output is correct
15 Correct 23 ms 13520 KB Output is correct
16 Correct 34 ms 14980 KB Output is correct
17 Correct 47 ms 16520 KB Output is correct
18 Correct 50 ms 16584 KB Output is correct
19 Correct 50 ms 16576 KB Output is correct
20 Correct 49 ms 16572 KB Output is correct
21 Correct 45 ms 16508 KB Output is correct
22 Correct 35 ms 16064 KB Output is correct
23 Correct 36 ms 16072 KB Output is correct
24 Correct 39 ms 16080 KB Output is correct
25 Correct 36 ms 16072 KB Output is correct
26 Correct 39 ms 16328 KB Output is correct
27 Correct 54 ms 16576 KB Output is correct
28 Correct 41 ms 16580 KB Output is correct
29 Correct 64 ms 16584 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10840 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10840 KB Output is correct
14 Correct 12 ms 12248 KB Output is correct
15 Correct 23 ms 13520 KB Output is correct
16 Correct 34 ms 14980 KB Output is correct
17 Correct 47 ms 16520 KB Output is correct
18 Correct 50 ms 16584 KB Output is correct
19 Correct 50 ms 16576 KB Output is correct
20 Correct 49 ms 16572 KB Output is correct
21 Correct 45 ms 16508 KB Output is correct
22 Correct 35 ms 16064 KB Output is correct
23 Correct 36 ms 16072 KB Output is correct
24 Correct 39 ms 16080 KB Output is correct
25 Correct 36 ms 16072 KB Output is correct
26 Correct 39 ms 16328 KB Output is correct
27 Correct 54 ms 16576 KB Output is correct
28 Correct 41 ms 16580 KB Output is correct
29 Correct 64 ms 16584 KB Output is correct
30 Correct 131 ms 42360 KB Output is correct
31 Correct 158 ms 43156 KB Output is correct
32 Correct 193 ms 44452 KB Output is correct
33 Correct 268 ms 46760 KB Output is correct
34 Correct 121 ms 42140 KB Output is correct
35 Correct 271 ms 47260 KB Output is correct
36 Correct 271 ms 47124 KB Output is correct
37 Correct 273 ms 47140 KB Output is correct
38 Correct 265 ms 47524 KB Output is correct
39 Correct 286 ms 47004 KB Output is correct
40 Correct 245 ms 46248 KB Output is correct
41 Correct 266 ms 46488 KB Output is correct
42 Correct 267 ms 47000 KB Output is correct
43 Correct 189 ms 46244 KB Output is correct
44 Correct 191 ms 46744 KB Output is correct
45 Correct 183 ms 45972 KB Output is correct
46 Correct 201 ms 45544 KB Output is correct
47 Correct 198 ms 45468 KB Output is correct
48 Correct 241 ms 46504 KB Output is correct
49 Correct 263 ms 47516 KB Output is correct