oj.uz

Submission #40268

# Submission time Handle Problem Language Result Execution time Memory
40268 2018-01-30T12:50:33 Z krauch Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 2000 ms 175836 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 = 1e6 + 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 > vec, g[N], qr[N];

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

    cin >> n >> Q;
    forn(i, 1, n) {
        cin >> a[i] >> b[i];
        if (a[i] > b[i]) {
            swap(a[i], b[i]);
            flip[i] = 1;
        }
        vec.eb(a[i]);
        vec.eb(b[i]);
    }

    forn(i, 1, Q) {
        cin >> c[i];
        vec.eb(c[i]);
    }

    sort(all(vec));
    vec.erase(unique(all(vec)), vec.end());

    forn(i, 1, n) {
        vala[i] = upper_bound(all(vec), a[i]) - vec.begin();
        valb[i] = upper_bound(all(vec), b[i]) - vec.begin();
        qr[valb[i]].eb(i);
    }

    forn(i, 1, Q) {
        c[i] = upper_bound(all(vec), c[i]) - vec.begin();
        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];
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 159988 KB Output is correct
2 Correct 79 ms 160776 KB Output is correct
3 Correct 109 ms 161692 KB Output is correct
4 Correct 138 ms 162220 KB Output is correct
5 Correct 125 ms 162220 KB Output is correct
6 Correct 150 ms 162220 KB Output is correct
7 Correct 134 ms 162220 KB Output is correct
8 Correct 115 ms 162220 KB Output is correct
9 Correct 94 ms 161956 KB Output is correct
10 Correct 88 ms 161956 KB Output is correct
11 Correct 83 ms 161824 KB Output is correct
12 Correct 108 ms 162088 KB Output is correct
13 Correct 113 ms 162088 KB Output is correct
14 Correct 123 ms 162220 KB Output is correct
15 Correct 141 ms 162220 KB Output is correct
16 Correct 139 ms 162220 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 166824 KB Output is correct
2 Correct 369 ms 169168 KB Output is correct
3 Correct 525 ms 170752 KB Output is correct
4 Correct 730 ms 175836 KB Output is correct
5 Execution timed out 2000 ms 166560 KB Execution timed out
6 Halted 0 ms 0 KB -