oj.uz

Submission #40273

# Submission time Handle Problem Language Result Execution time Memory
40273 2018-01-30T13:10:02 Z krauch Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 490 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, 1, 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 96492 KB Output is correct
2 Correct 7 ms 96492 KB Output is correct
3 Incorrect 10 ms 96500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 97224 KB Output is correct
2 Correct 55 ms 98140 KB Output is correct
3 Correct 84 ms 99312 KB Output is correct
4 Correct 96 ms 99840 KB Output is correct
5 Correct 96 ms 99840 KB Output is correct
6 Correct 74 ms 99840 KB Output is correct
7 Correct 85 ms 99840 KB Output is correct
8 Correct 74 ms 99840 KB Output is correct
9 Correct 53 ms 99576 KB Output is correct
10 Correct 55 ms 99576 KB Output is correct
11 Correct 45 ms 99444 KB Output is correct
12 Correct 63 ms 99708 KB Output is correct
13 Incorrect 64 ms 99708 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 104956 KB Output is correct
2 Correct 247 ms 108324 KB Output is correct
3 Correct 292 ms 109908 KB Output is correct
4 Correct 450 ms 117040 KB Output is correct
5 Correct 150 ms 104692 KB Output is correct
6 Correct 490 ms 117040 KB Output is correct
7 Incorrect 454 ms 117040 KB Output isn't correct
8 Halted 0 ms 0 KB -