oj.uz

Submission #916721

# Submission time Handle Problem Language Result Execution time Memory
916721 2024-01-26T11:05:48 Z Dec0Dedd Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 2195 ms 106676 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() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    int t=1; //cin>>t;
    while (t--) solve();
}

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 6 ms 14684 KB Output is correct
4 Correct 6 ms 14680 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 7 ms 14684 KB Output is correct
8 Correct 8 ms 14684 KB Output is correct
9 Correct 5 ms 14740 KB Output is correct
10 Correct 6 ms 14460 KB Output is correct
11 Correct 6 ms 14424 KB Output is correct
12 Correct 5 ms 14680 KB Output is correct
13 Correct 6 ms 14428 KB Output is correct
14 Correct 36 ms 18860 KB Output is correct
15 Correct 94 ms 23532 KB Output is correct
16 Correct 140 ms 28084 KB Output is correct
17 Correct 252 ms 32768 KB Output is correct
18 Correct 156 ms 32664 KB Output is correct
19 Correct 233 ms 32696 KB Output is correct
20 Correct 176 ms 32492 KB Output is correct
21 Correct 155 ms 32468 KB Output is correct
22 Correct 123 ms 27068 KB Output is correct
23 Correct 105 ms 24348 KB Output is correct
24 Correct 79 ms 22096 KB Output is correct
25 Correct 112 ms 28620 KB Output is correct
26 Correct 109 ms 25848 KB Output is correct
27 Correct 141 ms 26980 KB Output is correct
28 Correct 102 ms 26824 KB Output is correct
29 Correct 173 ms 29812 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 6 ms 14684 KB Output is correct
4 Correct 6 ms 14680 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 7 ms 14684 KB Output is correct
8 Correct 8 ms 14684 KB Output is correct
9 Correct 5 ms 14740 KB Output is correct
10 Correct 6 ms 14460 KB Output is correct
11 Correct 6 ms 14424 KB Output is correct
12 Correct 5 ms 14680 KB Output is correct
13 Correct 6 ms 14428 KB Output is correct
14 Correct 36 ms 18860 KB Output is correct
15 Correct 94 ms 23532 KB Output is correct
16 Correct 140 ms 28084 KB Output is correct
17 Correct 252 ms 32768 KB Output is correct
18 Correct 156 ms 32664 KB Output is correct
19 Correct 233 ms 32696 KB Output is correct
20 Correct 176 ms 32492 KB Output is correct
21 Correct 155 ms 32468 KB Output is correct
22 Correct 123 ms 27068 KB Output is correct
23 Correct 105 ms 24348 KB Output is correct
24 Correct 79 ms 22096 KB Output is correct
25 Correct 112 ms 28620 KB Output is correct
26 Correct 109 ms 25848 KB Output is correct
27 Correct 141 ms 26980 KB Output is correct
28 Correct 102 ms 26824 KB Output is correct
29 Correct 173 ms 29812 KB Output is correct
30 Correct 532 ms 47864 KB Output is correct
31 Correct 851 ms 59960 KB Output is correct
32 Correct 917 ms 76420 KB Output is correct
33 Correct 1971 ms 105552 KB Output is correct
34 Correct 403 ms 45136 KB Output is correct
35 Correct 1992 ms 106676 KB Output is correct
36 Correct 1799 ms 106432 KB Output is correct
37 Correct 2195 ms 105696 KB Output is correct
38 Correct 1898 ms 106064 KB Output is correct
39 Correct 1813 ms 106320 KB Output is correct
40 Correct 1638 ms 106164 KB Output is correct
41 Correct 2059 ms 106528 KB Output is correct
42 Correct 1691 ms 106028 KB Output is correct
43 Correct 874 ms 105988 KB Output is correct
44 Correct 908 ms 105984 KB Output is correct
45 Correct 865 ms 106008 KB Output is correct
46 Correct 728 ms 63736 KB Output is correct
47 Correct 602 ms 49748 KB Output is correct
48 Correct 1010 ms 77800 KB Output is correct
49 Correct 1006 ms 77488 KB Output is correct