Submission #519767

#	Time	Username	Problem	Language	Result	Execution time	Memory
519767		byunjaewoo	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1754 ms	124484 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65