Submission #423338

#	Time	Username	Problem	Language	Result	Execution time	Memory
423338		Osama_Alkhodairy	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	2004 ms	69660 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define finish(x) return cout << x << endl, 0;
 
struct fenwick{
    int n, fen[600005];
    void resize(int _n){
        n = _n + 1;
        memset(fen, 0, sizeof fen);
    }
    int query(int ind){
        int ans = 0;
        while(ind >= 1){
            ans += fen[ind];
            ind -= ind & -ind;
        }
        return ans;
    }
    void update(int ind, ll val){
        while(ind <= n){
            fen[ind] += val;
            ind += ind & -ind;
        }
    }
    int query(int l, int r){
        return query(r) - query(l - 1);
    }
};
struct segment{
    int n, seg[1200000];
    void resize(int _n){
        n = _n;
        memset(seg, -1, sizeof seg);
    }
    void modify(int p, int val){
        for(seg[p += n] = val ; p > 1 ; p >>= 1)
            seg[p >> 1] = max(seg[p], seg[p ^ 1]);
    }
    int query(int l, int r){
        r++;
        int ret = -1;
        for(l += n, r += n ; l < r ; l >>= 1, r >>= 1){
            if(l & 1) ret = max(ret, seg[l++]);
            if(r & 1) ret = max(ret, seg[--r]);
        }
        return ret;
    }
};
 
int n, k, x, y, mx;
vector <int> a, b, c;
vector <pair <int, int> > q[200001];
map <int, int> com, decode;
segment seg;
fenwick fen;
 
int main(){
    scanf("%d %d", &n, &k);
    for(int i = 0 ; i < n && scanf("%d %d", &x, &y) ; i++)
        a.push_back(x), b.push_back(y), com[x] = com[y] = 1;
    for(int i = 0 ; i < k && scanf("%d", &x) ; i++)
        c.push_back(x), com[x] = 1;
    x = 1;
    for(auto &i : com) i.second = x++;
    for(auto &i : a){
        decode[com[i]] = i;
        i = com[i];
    }
    for(auto &i : b){
        decode[com[i]] = i;
        i = com[i];
    }
    for(auto &i : c) i = com[i];
    mx = 2 * n + k + 1;
    seg.resize(mx);
    fen.resize(mx);
    for(int i = 0 ; i < k ; i++)
        seg.modify(c[i], i);
    for(int i = 0 ; i < n ; i++){
        int ind = seg.query(min(a[i], b[i]), max(a[i], b[i]) - 1);
        q[ind + 1].push_back(make_pair(max(a[i], b[i]), i));
        if(ind != -1 && b[i] > a[i])
            swap(a[i], b[i]);
    }
    for(int i = k - 1 ; i >= 0 ; i--){
        fen.update(c[i], 1);
        for(auto &j : q[i]){
            int val = fen.query(j.first, mx);
            if(val % 2) swap(a[j.second], b[j.second]);
        }
    }
    ll ans = 0;
    for(auto &i : a) ans += decode[i];
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~

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