oj.uz

Submission #62521

# Submission time Handle Problem Language Result Execution time Memory
62521 2018-07-28T22:15:04 Z Osama_Alkhodairy Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 3000 ms 101808 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]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12280 KB Output is correct
2 Correct 18 ms 12280 KB Output is correct
3 Correct 16 ms 12492 KB Output is correct
4 Correct 20 ms 12492 KB Output is correct
5 Correct 24 ms 12492 KB Output is correct
6 Correct 18 ms 12640 KB Output is correct
7 Correct 19 ms 12640 KB Output is correct
8 Correct 18 ms 12640 KB Output is correct
9 Correct 17 ms 12780 KB Output is correct
10 Correct 17 ms 12780 KB Output is correct
11 Correct 17 ms 12780 KB Output is correct
12 Correct 18 ms 12876 KB Output is correct
13 Correct 17 ms 12876 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12280 KB Output is correct
2 Correct 18 ms 12280 KB Output is correct
3 Correct 16 ms 12492 KB Output is correct
4 Correct 20 ms 12492 KB Output is correct
5 Correct 24 ms 12492 KB Output is correct
6 Correct 18 ms 12640 KB Output is correct
7 Correct 19 ms 12640 KB Output is correct
8 Correct 18 ms 12640 KB Output is correct
9 Correct 17 ms 12780 KB Output is correct
10 Correct 17 ms 12780 KB Output is correct
11 Correct 17 ms 12780 KB Output is correct
12 Correct 18 ms 12876 KB Output is correct
13 Correct 17 ms 12876 KB Output is correct
14 Correct 82 ms 15532 KB Output is correct
15 Correct 183 ms 18768 KB Output is correct
16 Correct 320 ms 22224 KB Output is correct
17 Correct 445 ms 25860 KB Output is correct
18 Correct 480 ms 27096 KB Output is correct
19 Correct 476 ms 28284 KB Output is correct
20 Correct 474 ms 29384 KB Output is correct
21 Correct 464 ms 30764 KB Output is correct
22 Correct 206 ms 30764 KB Output is correct
23 Correct 179 ms 30764 KB Output is correct
24 Correct 149 ms 30764 KB Output is correct
25 Correct 213 ms 32292 KB Output is correct
26 Correct 227 ms 32292 KB Output is correct
27 Correct 260 ms 32292 KB Output is correct
28 Correct 237 ms 32960 KB Output is correct
29 Correct 414 ms 35984 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12280 KB Output is correct
2 Correct 18 ms 12280 KB Output is correct
3 Correct 16 ms 12492 KB Output is correct
4 Correct 20 ms 12492 KB Output is correct
5 Correct 24 ms 12492 KB Output is correct
6 Correct 18 ms 12640 KB Output is correct
7 Correct 19 ms 12640 KB Output is correct
8 Correct 18 ms 12640 KB Output is correct
9 Correct 17 ms 12780 KB Output is correct
10 Correct 17 ms 12780 KB Output is correct
11 Correct 17 ms 12780 KB Output is correct
12 Correct 18 ms 12876 KB Output is correct
13 Correct 17 ms 12876 KB Output is correct
14 Correct 82 ms 15532 KB Output is correct
15 Correct 183 ms 18768 KB Output is correct
16 Correct 320 ms 22224 KB Output is correct
17 Correct 445 ms 25860 KB Output is correct
18 Correct 480 ms 27096 KB Output is correct
19 Correct 476 ms 28284 KB Output is correct
20 Correct 474 ms 29384 KB Output is correct
21 Correct 464 ms 30764 KB Output is correct
22 Correct 206 ms 30764 KB Output is correct
23 Correct 179 ms 30764 KB Output is correct
24 Correct 149 ms 30764 KB Output is correct
25 Correct 213 ms 32292 KB Output is correct
26 Correct 227 ms 32292 KB Output is correct
27 Correct 260 ms 32292 KB Output is correct
28 Correct 237 ms 32960 KB Output is correct
29 Correct 414 ms 35984 KB Output is correct
30 Correct 675 ms 41936 KB Output is correct
31 Correct 1068 ms 53220 KB Output is correct
32 Correct 1706 ms 67320 KB Output is correct
33 Correct 2815 ms 94308 KB Output is correct
34 Correct 436 ms 94308 KB Output is correct
35 Execution timed out 3028 ms 101808 KB Time limit exceeded
36 Halted 0 ms 0 KB -