oj.uz

Submission #916719

# Submission time Handle Problem Language Result Execution time Memory
916719 2024-01-26T11:05:06 Z Dec0Dedd Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 2193 ms 112332 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pp;

const int N = 2e5+10;
const int X = 3*N;

int x[N], y[N], a[N], b[N], t[N], n, k;

struct segtree {
    vector<int> t;

    void init(int sz) {
        t.resize(4*sz+1);
    }

    void upd(int v, int l, int r, int p, int vl) {
        if (l == r) {
            t[v]=max(vl, t[v]);
            return;
        } int m=(l+r)/2;
        if (p <= m) upd(2*v, l, m, p, vl);
        else upd(2*v+1, m+1, r, p, vl);
        t[v]=max(t[2*v], t[2*v+1]);
    }

    int que(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return t[v];
        int m=(l+r)/2;
        return max(que(2*v, l, m, ql, qr), que(2*v+1, m+1, r, ql, qr));
    }
};

struct fenwick {
    vector<int> bit;
    int n;

    void init(int sz) {
        n=sz+10;
        bit.assign(n, 0);
    }

    int sum(int r) {
        int res=0;
        for (;r>=0; r=(r&(r+1))-1) res+=bit[r];
        return res;
    }

    int que(int l, int r) {
        return sum(r)-sum(l-1);
    }

    void upd(int x, int d) {
        for (; x<n; x=x|(x+1)) bit[x]+=d;
    }
};

void solve() {
    cin>>n>>k;

    map<int, int> sc, resc;
    set<int> st;
    for (int i=1; i<=n; ++i) {
        cin>>x[i]>>y[i];
        st.insert(x[i]), st.insert(y[i]);
    }

    for (int i=1; i<=k; ++i) {
        cin>>t[i];
        st.insert(t[i]);
    }

    int i=1;
    for (auto u : st) sc[u]=i, resc[i++]=u;
    for (int i=1; i<=n; ++i) {
        x[i]=sc[x[i]], y[i]=sc[y[i]];
        a[i]=min(x[i], y[i]), b[i]=max(x[i], y[i]);
    }

    segtree tr; tr.init(X+10);
    for (int i=1; i<=k; ++i) t[i]=sc[t[i]], tr.upd(1, 1, X, t[i], i);

    vector<pp> v;
    for (int i=1; i<=n; ++i) {
        int j=tr.que(1, 1, X, a[i], b[i]-1);
        v.push_back({b[i], {-(j+1), i}});
    }

    for (int i=1; i<=k; ++i) v.push_back({t[i], {i, 0}});
    sort(v.begin(), v.end(), greater<pp>());

    fenwick fw; fw.init(X);
    ll ans=0;
    for (auto u : v) {
        if (u.second.first < 0) {
            int j=-u.second.first;
            int vv=fw.que(j, k);

            int vl;
            if (j == 1) {
                if (vv%2) vl=y[u.second.second];
                else vl=x[u.second.second];
            } else {
                if (vv%2) vl=a[u.second.second];
                else vl=b[u.second.second];
            } ans+=resc[vl];
        } else {
            fw.upd(u.second.first, 1);
        }
    } cout<<ans<<"\n";
}

int main() {
    int t=1; //cin>>t;
    while (t--) solve();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14424 KB Output is correct
2 Correct 5 ms 14512 KB Output is correct
3 Correct 6 ms 14684 KB Output is correct
4 Correct 7 ms 14684 KB Output is correct
5 Correct 6 ms 14552 KB Output is correct
6 Correct 8 ms 14684 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 7 ms 14684 KB Output is correct
9 Correct 6 ms 14520 KB Output is correct
10 Correct 6 ms 14428 KB Output is correct
11 Correct 6 ms 14408 KB Output is correct
12 Correct 6 ms 14428 KB Output is correct
13 Correct 7 ms 14424 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14424 KB Output is correct
2 Correct 5 ms 14512 KB Output is correct
3 Correct 6 ms 14684 KB Output is correct
4 Correct 7 ms 14684 KB Output is correct
5 Correct 6 ms 14552 KB Output is correct
6 Correct 8 ms 14684 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 7 ms 14684 KB Output is correct
9 Correct 6 ms 14520 KB Output is correct
10 Correct 6 ms 14428 KB Output is correct
11 Correct 6 ms 14408 KB Output is correct
12 Correct 6 ms 14428 KB Output is correct
13 Correct 7 ms 14424 KB Output is correct
14 Correct 42 ms 19024 KB Output is correct
15 Correct 96 ms 24008 KB Output is correct
16 Correct 132 ms 28732 KB Output is correct
17 Correct 223 ms 33668 KB Output is correct
18 Correct 247 ms 33664 KB Output is correct
19 Correct 189 ms 33608 KB Output is correct
20 Correct 186 ms 33652 KB Output is correct
21 Correct 183 ms 33808 KB Output is correct
22 Correct 125 ms 27520 KB Output is correct
23 Correct 108 ms 24744 KB Output is correct
24 Correct 91 ms 22728 KB Output is correct
25 Correct 131 ms 29196 KB Output is correct
26 Correct 118 ms 26824 KB Output is correct
27 Correct 155 ms 28104 KB Output is correct
28 Correct 129 ms 27980 KB Output is correct
29 Correct 166 ms 30868 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14424 KB Output is correct
2 Correct 5 ms 14512 KB Output is correct
3 Correct 6 ms 14684 KB Output is correct
4 Correct 7 ms 14684 KB Output is correct
5 Correct 6 ms 14552 KB Output is correct
6 Correct 8 ms 14684 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 7 ms 14684 KB Output is correct
9 Correct 6 ms 14520 KB Output is correct
10 Correct 6 ms 14428 KB Output is correct
11 Correct 6 ms 14408 KB Output is correct
12 Correct 6 ms 14428 KB Output is correct
13 Correct 7 ms 14424 KB Output is correct
14 Correct 42 ms 19024 KB Output is correct
15 Correct 96 ms 24008 KB Output is correct
16 Correct 132 ms 28732 KB Output is correct
17 Correct 223 ms 33668 KB Output is correct
18 Correct 247 ms 33664 KB Output is correct
19 Correct 189 ms 33608 KB Output is correct
20 Correct 186 ms 33652 KB Output is correct
21 Correct 183 ms 33808 KB Output is correct
22 Correct 125 ms 27520 KB Output is correct
23 Correct 108 ms 24744 KB Output is correct
24 Correct 91 ms 22728 KB Output is correct
25 Correct 131 ms 29196 KB Output is correct
26 Correct 118 ms 26824 KB Output is correct
27 Correct 155 ms 28104 KB Output is correct
28 Correct 129 ms 27980 KB Output is correct
29 Correct 166 ms 30868 KB Output is correct
30 Correct 525 ms 50624 KB Output is correct
31 Correct 756 ms 62888 KB Output is correct
32 Correct 1080 ms 80080 KB Output is correct
33 Correct 2089 ms 112008 KB Output is correct
34 Correct 444 ms 46804 KB Output is correct
35 Correct 2193 ms 111404 KB Output is correct
36 Correct 2029 ms 112332 KB Output is correct
37 Correct 2024 ms 112288 KB Output is correct
38 Correct 1925 ms 111404 KB Output is correct
39 Correct 2081 ms 111584 KB Output is correct
40 Correct 1752 ms 111076 KB Output is correct
41 Correct 2025 ms 112052 KB Output is correct
42 Correct 2021 ms 112160 KB Output is correct
43 Correct 1051 ms 110932 KB Output is correct
44 Correct 952 ms 111292 KB Output is correct
45 Correct 948 ms 110732 KB Output is correct
46 Correct 850 ms 68364 KB Output is correct
47 Correct 562 ms 53436 KB Output is correct
48 Correct 1299 ms 84168 KB Output is correct
49 Correct 1097 ms 83584 KB Output is correct