oj.uz

Submission #519767

# Submission time Handle Problem Language Result Execution time Memory
519767 2022-01-27T10:01:41 Z byunjaewoo Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1754 ms 124484 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int Nmax=200010, S=(1<<20);
int N, K;
int A[Nmax], B[Nmax], C[Nmax];
ll inv[3*Nmax];
ll ans;
int cnt;
set<int> St;
map<int, int> Mp;
class Seg {
public:
    void Update(int k, int v) {Update(1, 1, S, k, v);}
    int Query(int l, int r) {return Query(1, 1, S, l, r);}
private:
    int Tree[2*S];
    void Update(int node, int s, int e, int k, int v) {
        if(s==e) {
            Tree[node]=max(Tree[node], v);
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, v);
        else Update(rch, m+1, e, k, v);
        Tree[node]=max(Tree[lch], Tree[rch]);
    }
    int Query(int node, int s, int e, int l, int r) {
        if(l>e || s>r) return 0;
        if(l<=s && e<=r) return Tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        return max(Query(lch, s, m, l, r), Query(rch, m+1, e, l, r));
    }
}T;
class PST {
public:
    PST() {
        root[cnt++]=0;
        Tree[bcnt++]={0, 0, 0};
    }
    void Update(int k) {
        root[cnt]=Update(root[cnt-1], 1, S, k);
        cnt++;
    }
    int Query(int l, int r, int v) {return Query(root[l-1], root[r], 1, S, v, S);}
private:
    struct Node {int l, r, v;};
    Node Tree[70101010];
    int bcnt, cnt, root[Nmax];
    int Update(int prev, int s, int e, int k) {
        int curr=bcnt++;
        Tree[curr].v=Tree[prev].v+1;
        if(s==e) return curr;
        int m=(s+e)/2;
        if(k<=m) {
            Tree[curr].l=Update(Tree[prev].l, s, m, k);
            Tree[curr].r=Tree[prev].r;
        }
        else {
            Tree[curr].l=Tree[prev].l;
            Tree[curr].r=Update(Tree[prev].r, m+1, e, k);
        }
        Tree[curr].v=Tree[Tree[curr].l].v+Tree[Tree[curr].r].v;
        return curr;
    }
    int Query(int lnode, int rnode, int s, int e, int l, int r) {
        if(l<=s && e<=r) return Tree[rnode].v-Tree[lnode].v;
        if(l>e || s>r) return 0;
        int m=(s+e)/2;
        return Query(Tree[lnode].l, Tree[rnode].l, s, m, l, r)
               +Query(Tree[lnode].r, Tree[rnode].r, m+1, e, l, r);
    }
}P;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>K;
    for(int i=1; i<=N; i++) {
        cin>>A[i]>>B[i];
        St.insert(A[i]); St.insert(B[i]);
    }
    for(int i=1; i<=K; i++) {
        cin>>C[i];
        St.insert(C[i]);
    }
    for(int i:St) Mp[i]=++cnt, inv[cnt]=i;
    for(int i=1; i<=K; i++) {
        T.Update(Mp[C[i]], i);
        P.Update(Mp[C[i]]);
    }
    for(int i=1; i<=N; i++) {
        int m=Mp[min(A[i], B[i])], M=Mp[max(A[i], B[i])];
        int e=T.Query(m, M-1), k=P.Query(e+1, K, M);
        if(!e) m=Mp[B[i]], M=Mp[A[i]];
        if(k%2) ans+=inv[m];
        else ans+=inv[M];
    }
    cout<<ans;
    return 0;
}

Compilation message

fortune_telling2.cpp: In constructor 'PST::PST()':
fortune_telling2.cpp:39:14: warning: '*<unknown>.PST::cnt' is used uninitialized in this function [-Wuninitialized]
   39 |         root[cnt++]=0;
      |              ^~~
fortune_telling2.cpp:40:14: warning: '*<unknown>.PST::bcnt' is used uninitialized in this function [-Wuninitialized]
   40 |         Tree[bcnt++]={0, 0, 0};
      |              ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 868 KB Output is correct
3 Correct 3 ms 988 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 3 ms 972 KB Output is correct
8 Correct 3 ms 988 KB Output is correct
9 Correct 2 ms 972 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 2 ms 844 KB Output is correct
13 Correct 3 ms 844 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 868 KB Output is correct
3 Correct 3 ms 988 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 3 ms 972 KB Output is correct
8 Correct 3 ms 988 KB Output is correct
9 Correct 2 ms 972 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 2 ms 844 KB Output is correct
13 Correct 3 ms 844 KB Output is correct
14 Correct 36 ms 6608 KB Output is correct
15 Correct 67 ms 12760 KB Output is correct
16 Correct 128 ms 19012 KB Output is correct
17 Correct 179 ms 25160 KB Output is correct
18 Correct 180 ms 25156 KB Output is correct
19 Correct 176 ms 25124 KB Output is correct
20 Correct 166 ms 25176 KB Output is correct
21 Correct 176 ms 25160 KB Output is correct
22 Correct 110 ms 20292 KB Output is correct
23 Correct 105 ms 18300 KB Output is correct
24 Correct 84 ms 16472 KB Output is correct
25 Correct 114 ms 21508 KB Output is correct
26 Correct 108 ms 19876 KB Output is correct
27 Correct 135 ms 20804 KB Output is correct
28 Correct 116 ms 20828 KB Output is correct
29 Correct 151 ms 22876 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 868 KB Output is correct
3 Correct 3 ms 988 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 3 ms 972 KB Output is correct
8 Correct 3 ms 988 KB Output is correct
9 Correct 2 ms 972 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 2 ms 844 KB Output is correct
13 Correct 3 ms 844 KB Output is correct
14 Correct 36 ms 6608 KB Output is correct
15 Correct 67 ms 12760 KB Output is correct
16 Correct 128 ms 19012 KB Output is correct
17 Correct 179 ms 25160 KB Output is correct
18 Correct 180 ms 25156 KB Output is correct
19 Correct 176 ms 25124 KB Output is correct
20 Correct 166 ms 25176 KB Output is correct
21 Correct 176 ms 25160 KB Output is correct
22 Correct 110 ms 20292 KB Output is correct
23 Correct 105 ms 18300 KB Output is correct
24 Correct 84 ms 16472 KB Output is correct
25 Correct 114 ms 21508 KB Output is correct
26 Correct 108 ms 19876 KB Output is correct
27 Correct 135 ms 20804 KB Output is correct
28 Correct 116 ms 20828 KB Output is correct
29 Correct 151 ms 22876 KB Output is correct
30 Correct 487 ms 77476 KB Output is correct
31 Correct 670 ms 87400 KB Output is correct
32 Correct 962 ms 99824 KB Output is correct
33 Correct 1551 ms 124484 KB Output is correct
34 Correct 497 ms 75076 KB Output is correct
35 Correct 1681 ms 124336 KB Output is correct
36 Correct 1754 ms 124228 KB Output is correct
37 Correct 1648 ms 124416 KB Output is correct
38 Correct 1574 ms 124256 KB Output is correct
39 Correct 1526 ms 124404 KB Output is correct
40 Correct 1313 ms 124008 KB Output is correct
41 Correct 1498 ms 124420 KB Output is correct
42 Correct 1532 ms 124344 KB Output is correct
43 Correct 777 ms 121956 KB Output is correct
44 Correct 807 ms 122296 KB Output is correct
45 Correct 777 ms 122964 KB Output is correct
46 Correct 716 ms 89668 KB Output is correct
47 Correct 608 ms 78600 KB Output is correct
48 Correct 937 ms 102628 KB Output is correct
49 Correct 905 ms 102596 KB Output is correct