Submission #40274

#	Time	Username	Problem	Language	Result	Execution time	Memory
40274		krauch	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	460 ms	117040 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65