oj.uz

Submission #40274

# Submission time Handle Problem Language Result Execution time Memory
40274 2018-01-30T13:10:47 Z krauch Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 460 ms 117040 KB 
#include <bits/stdc++.h>

#include <stdio.h>
#include <stdlib.h>

using namespace std;

typedef long long ll;

#define mkp make_pair
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define eb emplace_back
#define F first
#define S second
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

const ll ool = 1e18 + 9;
const int N = 6e5 + 6, C = 21, oo = 1e9 + 9;

int n, Q, a[N], b[N], c[N], vala[N], valb[N], t[N], mx[C][N], lg[N];
bool flip[N];
ll ans;
vector < int > g[N], qr[N];
vector < pair < int, int > > vec;

void upd(int i) {
    for (; i <= sz(vec); i |= i + 1) t[i]++;
}

int get(int i) {
    int res = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1) res += t[i];
    return res;
}

int getmx(int l, int r) {
    if (l > r) return 0;
    int deg = lg[r - l + 1];
    return max(mx[deg][l], mx[deg][r - (1 << deg) + 1]);
}

int main() {

    #ifdef krauch
        freopen("input.txt", "r", stdin);
    #endif

    scanf("%d%d", &n, &Q);
    forn(i, 1, n) {
        scanf("%d%d", a + i, b + i);
        if (a[i] > b[i]) {
            swap(a[i], b[i]);
            flip[i] = 1;
        }
        vec.eb(a[i], i);
        vec.eb(b[i], n + i);
    }

    forn(i, 1, Q) {
        scanf("%d", c + i);
        vec.eb(c[i], 2 * n + i);
    }

    sort(all(vec));

    int cnt = 1;
    forn(i, 0, sz(vec) - 1) {
        if (i && vec[i - 1].F != vec[i].F) ++cnt;
        if (vec[i].S <= n) vala[vec[i].S] = cnt;
        else if (vec[i].S <= 2 * n) valb[vec[i].S - n] = cnt;
        else c[vec[i].S - 2 * n] = cnt;
    }

    forn(i, 1, n) {
        qr[valb[i]].eb(i);
    }

    forn(i, 1, Q) {
        g[c[i]].eb(i);
        mx[0][c[i]] = i;
    }

    forn(i, 1, C) {
        forn(j, 1, sz(vec) - (1 << i) + 1) {
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
        }
    }
    forn(i, 2, sz(vec)) lg[i] = lg[i >> 1] + 1;

    for1(i, sz(vec), 1) {
        for (auto it : g[i]) {
            upd(sz(vec) - it);
        }
        for (auto it : qr[i]) {
            int kek = getmx(vala[it], valb[it] - 1);
            if (kek == 0) {
                if ((get(sz(vec)) & 1) ^ flip[it]) ans += b[it];
                else ans += a[it];
            }
            else {
                if (get(sz(vec) - kek) & 1) ans += a[it];
                else ans += b[it];
            }
        }
    }

    printf("%lld\n", ans);

    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:50:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &Q);
                          ^
fortune_telling2.cpp:52:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", a + i, b + i);
                                    ^
fortune_telling2.cpp:62:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", c + i);
                           ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 96492 KB Output is correct
2 Correct 14 ms 96492 KB Output is correct
3 Correct 9 ms 96500 KB Output is correct
4 Correct 16 ms 96500 KB Output is correct
5 Correct 7 ms 96500 KB Output is correct
6 Correct 10 ms 96500 KB Output is correct
7 Correct 6 ms 96500 KB Output is correct
8 Correct 7 ms 96500 KB Output is correct
9 Correct 6 ms 96500 KB Output is correct
10 Correct 6 ms 96500 KB Output is correct
11 Correct 9 ms 96500 KB Output is correct
12 Correct 6 ms 96500 KB Output is correct
13 Correct 11 ms 96500 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 97224 KB Output is correct
2 Correct 39 ms 98140 KB Output is correct
3 Correct 56 ms 99312 KB Output is correct
4 Correct 67 ms 99840 KB Output is correct
5 Correct 67 ms 99840 KB Output is correct
6 Correct 71 ms 99840 KB Output is correct
7 Correct 82 ms 99840 KB Output is correct
8 Correct 66 ms 99840 KB Output is correct
9 Correct 47 ms 99576 KB Output is correct
10 Correct 54 ms 99576 KB Output is correct
11 Correct 58 ms 99444 KB Output is correct
12 Correct 42 ms 99708 KB Output is correct
13 Correct 65 ms 99708 KB Output is correct
14 Correct 96 ms 99840 KB Output is correct
15 Correct 59 ms 99840 KB Output is correct
16 Correct 73 ms 99840 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 104956 KB Output is correct
2 Correct 223 ms 108324 KB Output is correct
3 Correct 296 ms 109908 KB Output is correct
4 Correct 444 ms 117040 KB Output is correct
5 Correct 137 ms 104692 KB Output is correct
6 Correct 432 ms 117040 KB Output is correct
7 Correct 460 ms 117040 KB Output is correct
8 Correct 447 ms 117040 KB Output is correct
9 Correct 449 ms 117040 KB Output is correct
10 Correct 442 ms 117040 KB Output is correct
11 Correct 404 ms 117040 KB Output is correct
12 Correct 429 ms 117040 KB Output is correct
13 Correct 428 ms 117040 KB Output is correct
14 Correct 260 ms 117040 KB Output is correct
15 Correct 299 ms 117040 KB Output is correct
16 Correct 276 ms 117040 KB Output is correct
17 Correct 256 ms 115324 KB Output is correct
18 Correct 253 ms 114796 KB Output is correct
19 Correct 381 ms 117040 KB Output is correct
20 Correct 434 ms 117040 KB Output is correct