oj.uz

Submission #76489

# Submission time Handle Problem Language Result Execution time Memory
76489 2018-09-13T17:07:50 Z win11905 Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 1892 ms 27852 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define long long long
#define pii pair<int, int>
#define x first
#define y second

const int N = 2e5+5;

int n, k, t[N];
long ans;
vector<pii> que;
vector<int> coor, z[N];

int A[N], l[N], r[N];

void update(int x) {
    for(int i = x; i; i -= i & -i) t[i]++;
}

int query(int x) {
    int v = 0;
    for(int i = x; i <= coor.size() + 1; i += i & -i) v += t[i];
    return v;
}

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0, a, b; i < n; ++i) {
        scanf("%d %d", &a, &b);
        que.emplace_back(a, b);
        r[i] = k;
    }
    coor.resize(1);
    for(int i = 1; i <= k; ++i) {
        scanf("%d", A+i);
        coor.emplace_back(A[i]);
    }
    sort(all(coor));
    coor.resize(unique(all(coor)) - coor.begin());
    for(int i = 0; i <= k; ++i) A[i] = upper_bound(all(coor), A[i]) - coor.begin();
    auto f = [&](int v) int { return query(lower_bound(all(coor), v) - coor.begin() + 1); };
    for(int it = 0; it < 18; ++it) {
        for(int i = 0; i < n; ++i) if(l[i] < r[i]) z[l[i] + r[i] + 1 >> 1].emplace_back(i);
        for(int i = k; ~i; --i) {
            update(A[i]);
            for(auto v : z[i]) {
                if(f(que[v].x) != f(que[v].y)) l[v] = i;
                else r[v] = i-1;
            }
            z[i].clear();
        }
        memset(t, 0, sizeof t);
    }
    for(int i = 0; i < n; ++i) z[l[i]].emplace_back(i);
    for(int i = k; ~i; --i) {
        update(A[i]);
        for(auto v : z[i]) {
            int a, b; tie(a, b) = que[v];
            if(i == 0) ans += f(a) & 1 ? b : a;
            else ans += f(max(a, b)) & 1 ? min(a, b) : max(a, b);
        }
    } 
    printf("%lld\n", ans);
}

Compilation message

fortune_telling2.cpp: In function 'int query(int)':
fortune_telling2.cpp:25:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = x; i <= coor.size() + 1; i += i & -i) v += t[i];
                    ~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:46:66: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         for(int i = 0; i < n; ++i) if(l[i] < r[i]) z[l[i] + r[i] + 1 >> 1].emplace_back(i);
                                                      ~~~~~~~~~~~~^~~
fortune_telling2.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+i);
         ~~~~~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 10 ms 6016 KB Output is correct
3 Correct 10 ms 6016 KB Output is correct
4 Correct 10 ms 6016 KB Output is correct
5 Correct 11 ms 6016 KB Output is correct
6 Correct 11 ms 6140 KB Output is correct
7 Correct 11 ms 6140 KB Output is correct
8 Correct 10 ms 6140 KB Output is correct
9 Correct 8 ms 6140 KB Output is correct
10 Correct 10 ms 6140 KB Output is correct
11 Correct 11 ms 6168 KB Output is correct
12 Correct 11 ms 6168 KB Output is correct
13 Correct 10 ms 6168 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 10 ms 6016 KB Output is correct
3 Correct 10 ms 6016 KB Output is correct
4 Correct 10 ms 6016 KB Output is correct
5 Correct 11 ms 6016 KB Output is correct
6 Correct 11 ms 6140 KB Output is correct
7 Correct 11 ms 6140 KB Output is correct
8 Correct 10 ms 6140 KB Output is correct
9 Correct 8 ms 6140 KB Output is correct
10 Correct 10 ms 6140 KB Output is correct
11 Correct 11 ms 6168 KB Output is correct
12 Correct 11 ms 6168 KB Output is correct
13 Correct 10 ms 6168 KB Output is correct
14 Correct 55 ms 7020 KB Output is correct
15 Correct 112 ms 7912 KB Output is correct
16 Correct 174 ms 8800 KB Output is correct
17 Correct 255 ms 9868 KB Output is correct
18 Correct 245 ms 9868 KB Output is correct
19 Correct 250 ms 9868 KB Output is correct
20 Correct 248 ms 9868 KB Output is correct
21 Correct 245 ms 9868 KB Output is correct
22 Correct 139 ms 10004 KB Output is correct
23 Correct 141 ms 10004 KB Output is correct
24 Correct 142 ms 10004 KB Output is correct
25 Correct 126 ms 10004 KB Output is correct
26 Correct 152 ms 10004 KB Output is correct
27 Correct 212 ms 10044 KB Output is correct
28 Correct 172 ms 10044 KB Output is correct
29 Correct 246 ms 10188 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 10 ms 6016 KB Output is correct
3 Correct 10 ms 6016 KB Output is correct
4 Correct 10 ms 6016 KB Output is correct
5 Correct 11 ms 6016 KB Output is correct
6 Correct 11 ms 6140 KB Output is correct
7 Correct 11 ms 6140 KB Output is correct
8 Correct 10 ms 6140 KB Output is correct
9 Correct 8 ms 6140 KB Output is correct
10 Correct 10 ms 6140 KB Output is correct
11 Correct 11 ms 6168 KB Output is correct
12 Correct 11 ms 6168 KB Output is correct
13 Correct 10 ms 6168 KB Output is correct
14 Correct 55 ms 7020 KB Output is correct
15 Correct 112 ms 7912 KB Output is correct
16 Correct 174 ms 8800 KB Output is correct
17 Correct 255 ms 9868 KB Output is correct
18 Correct 245 ms 9868 KB Output is correct
19 Correct 250 ms 9868 KB Output is correct
20 Correct 248 ms 9868 KB Output is correct
21 Correct 245 ms 9868 KB Output is correct
22 Correct 139 ms 10004 KB Output is correct
23 Correct 141 ms 10004 KB Output is correct
24 Correct 142 ms 10004 KB Output is correct
25 Correct 126 ms 10004 KB Output is correct
26 Correct 152 ms 10004 KB Output is correct
27 Correct 212 ms 10044 KB Output is correct
28 Correct 172 ms 10044 KB Output is correct
29 Correct 246 ms 10188 KB Output is correct
30 Correct 325 ms 10188 KB Output is correct
31 Correct 650 ms 12308 KB Output is correct
32 Correct 1052 ms 16980 KB Output is correct
33 Correct 1874 ms 26028 KB Output is correct
34 Correct 240 ms 26028 KB Output is correct
35 Correct 1872 ms 26144 KB Output is correct
36 Correct 1892 ms 26488 KB Output is correct
37 Correct 1852 ms 26488 KB Output is correct
38 Correct 1851 ms 26488 KB Output is correct
39 Correct 1825 ms 26488 KB Output is correct
40 Correct 1445 ms 26488 KB Output is correct
41 Correct 1803 ms 26488 KB Output is correct
42 Correct 1788 ms 26488 KB Output is correct
43 Correct 640 ms 26488 KB Output is correct
44 Correct 657 ms 26488 KB Output is correct
45 Correct 641 ms 26488 KB Output is correct
46 Correct 849 ms 26488 KB Output is correct
47 Correct 903 ms 27852 KB Output is correct
48 Correct 1202 ms 27852 KB Output is correct
49 Correct 1144 ms 27852 KB Output is correct