oj.uz

Submission #423338

# Submission time Handle Problem Language Result Execution time Memory
423338 2021-06-11T02:16:52 Z Osama_Alkhodairy Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 2004 ms 69660 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12048 KB Output is correct
2 Correct 8 ms 12108 KB Output is correct
3 Correct 10 ms 12300 KB Output is correct
4 Correct 9 ms 12264 KB Output is correct
5 Correct 9 ms 12208 KB Output is correct
6 Correct 9 ms 12236 KB Output is correct
7 Correct 9 ms 12304 KB Output is correct
8 Correct 9 ms 12236 KB Output is correct
9 Correct 8 ms 12236 KB Output is correct
10 Correct 9 ms 12168 KB Output is correct
11 Correct 8 ms 12236 KB Output is correct
12 Correct 8 ms 12236 KB Output is correct
13 Correct 8 ms 12232 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12048 KB Output is correct
2 Correct 8 ms 12108 KB Output is correct
3 Correct 10 ms 12300 KB Output is correct
4 Correct 9 ms 12264 KB Output is correct
5 Correct 9 ms 12208 KB Output is correct
6 Correct 9 ms 12236 KB Output is correct
7 Correct 9 ms 12304 KB Output is correct
8 Correct 9 ms 12236 KB Output is correct
9 Correct 8 ms 12236 KB Output is correct
10 Correct 9 ms 12168 KB Output is correct
11 Correct 8 ms 12236 KB Output is correct
12 Correct 8 ms 12236 KB Output is correct
13 Correct 8 ms 12232 KB Output is correct
14 Correct 43 ms 14868 KB Output is correct
15 Correct 83 ms 17816 KB Output is correct
16 Correct 195 ms 20576 KB Output is correct
17 Correct 242 ms 23504 KB Output is correct
18 Correct 258 ms 23548 KB Output is correct
19 Correct 215 ms 23628 KB Output is correct
20 Correct 192 ms 23556 KB Output is correct
21 Correct 185 ms 23756 KB Output is correct
22 Correct 107 ms 21056 KB Output is correct
23 Correct 91 ms 19304 KB Output is correct
24 Correct 87 ms 17932 KB Output is correct
25 Correct 118 ms 21948 KB Output is correct
26 Correct 108 ms 18784 KB Output is correct
27 Correct 135 ms 19740 KB Output is correct
28 Correct 123 ms 19900 KB Output is correct
29 Correct 170 ms 21604 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12048 KB Output is correct
2 Correct 8 ms 12108 KB Output is correct
3 Correct 10 ms 12300 KB Output is correct
4 Correct 9 ms 12264 KB Output is correct
5 Correct 9 ms 12208 KB Output is correct
6 Correct 9 ms 12236 KB Output is correct
7 Correct 9 ms 12304 KB Output is correct
8 Correct 9 ms 12236 KB Output is correct
9 Correct 8 ms 12236 KB Output is correct
10 Correct 9 ms 12168 KB Output is correct
11 Correct 8 ms 12236 KB Output is correct
12 Correct 8 ms 12236 KB Output is correct
13 Correct 8 ms 12232 KB Output is correct
14 Correct 43 ms 14868 KB Output is correct
15 Correct 83 ms 17816 KB Output is correct
16 Correct 195 ms 20576 KB Output is correct
17 Correct 242 ms 23504 KB Output is correct
18 Correct 258 ms 23548 KB Output is correct
19 Correct 215 ms 23628 KB Output is correct
20 Correct 192 ms 23556 KB Output is correct
21 Correct 185 ms 23756 KB Output is correct
22 Correct 107 ms 21056 KB Output is correct
23 Correct 91 ms 19304 KB Output is correct
24 Correct 87 ms 17932 KB Output is correct
25 Correct 118 ms 21948 KB Output is correct
26 Correct 108 ms 18784 KB Output is correct
27 Correct 135 ms 19740 KB Output is correct
28 Correct 123 ms 19900 KB Output is correct
29 Correct 170 ms 21604 KB Output is correct
30 Correct 348 ms 26424 KB Output is correct
31 Correct 679 ms 35416 KB Output is correct
32 Correct 1016 ms 46776 KB Output is correct
33 Correct 1881 ms 69540 KB Output is correct
34 Correct 263 ms 24120 KB Output is correct
35 Correct 2004 ms 69660 KB Output is correct
36 Correct 1902 ms 69544 KB Output is correct
37 Correct 1947 ms 69384 KB Output is correct
38 Correct 1898 ms 69604 KB Output is correct
39 Correct 1945 ms 69232 KB Output is correct
40 Correct 1677 ms 68980 KB Output is correct
41 Correct 1850 ms 69340 KB Output is correct
42 Correct 1836 ms 69148 KB Output is correct
43 Correct 716 ms 68772 KB Output is correct
44 Correct 780 ms 68556 KB Output is correct
45 Correct 693 ms 68568 KB Output is correct
46 Correct 719 ms 48596 KB Output is correct
47 Correct 525 ms 38884 KB Output is correct
48 Correct 1012 ms 50688 KB Output is correct
49 Correct 989 ms 51020 KB Output is correct