Submission #567686

#	Time	Username	Problem	Language	Result	Execution time	Memory
567686		gg123_pe	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	11 ms	14828 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<ll,ll> ii; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

#define ff first 
#define ss second 

const int N = 2e5 + 5; 
const ll inf = 1e17 + 100; 


int n, k, a[N], b[N], t[N], id[N]; 
int st[3*N][20], root[3*N];
map <int,int> m; 
set <int> s; 
vector <int> adj[3*N], L, R, value; 

int maxi(int l, int r){
    int log = 31 - __builtin_clz(r-l+1);
    return max(st[l][log], st[r - (1<<log) + 1][log]); 
}
int createleaf(int x){
    L.push_back(-1), R.push_back(-1); 
    value.push_back(x); 
    return L.size() - 1; 
}
int createvertex(int u, int v){
    L.push_back(u), R.push_back(v); 
    value.push_back(value[u] + value[v]); 
    return L.size() - 1; 
}
int build(int l, int r){
    if(l == r) return createleaf(0); 
    int m = (l+r)>>1; 
    return createvertex(build(l, m), build(m+1, r)); 
}
int upd(int id, int l, int r, int x, int val){
    if(l == r) return createleaf(val); 
    int m = (l+r)>>1; 
    if(x <= m) return createvertex(upd(L[id], l, m, x, val), R[id]); 
    return createvertex(L[id], upd(R[id], m+1, r, x, val)); 
}
int get(int id, int l, int r, int x, int y){
    if(r < x or y < l) return 0; 
    if(x <= l and r <= y) return value[id]; 
    int m = (l+r)>>1; 
    return get(L[id], l, m, x, y) + get(R[id], m+1, r, x, y); 
}
int main(){
    cin >> n >> k; 

    f(i,1,n+1) {
        cin >> a[i] >> b[i]; 
        s.insert(a[i]), s.insert(b[i]); 
    }

    f(i,1,k+1) {
        cin >> t[i]; 
        s.insert(t[i]); 
    }

    int ID = 0; 
    for(int x: s) m[x] = ++ID; 

    f(i,1,k+1) {
        t[i] = m[t[i]]; 
        adj[t[i]].push_back(i); 
    }

    f(i,1,k+1) id[t[i]] = max(id[t[i]], i); 
    
    f(i,1,ID+1) st[i][0] = id[i]; 

    f(r,1,20){
        f(i,1,ID+1){
            int x = i + (1<<(r-1)); 
            if(x > ID) break;
            st[i][r] = max(st[i][r-1], st[x][r-1]); 
        }
    }

    root[ID+1] = build(0, k);
    fa(i,ID,0){
        root[i] = root[i+1];  
        for(int x: adj[i]) root[i] = upd(root[i], 0, k, x, 1);
    }

    ll ans = 0;

    f(i,1,n+1){
        int x = m[a[i]], y = m[b[i]]; 
        if(a[i] == b[i]){
            ans += (ll) a[i]; 
            continue; 
        }
        x = min(x, y), y = max(x, y); 
        int iq = maxi(x, y-1), s; 
        s = get(root[y], 0, k, iq+1, k);

        if(iq == 0){
            if(s&1) ans += (ll) b[i]; 
            else ans += (ll) a[i]; 
        }
        else{
            if(s&1)  ans += (ll) min(a[i], b[i]); 
            else ans += (ll) max(a[i], b[i]); 
        }
        
    }
    cout << ans << "\n"; 
    return 0; 
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65