oj.uz

Submission #40270

# Submission time Handle Problem Language Result Execution time Memory
40270 2018-01-30T12:54:36 Z krauch Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 2000 ms 112944 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 > 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

    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]);
        vec.eb(b[i]);
    }

    forn(i, 1, Q) {
        scanf("%d", 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];
            }
        }
    }

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

    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:49: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:51: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:61: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 6 ms 96360 KB Output is correct
2 Correct 6 ms 96492 KB Output is correct
3 Correct 6 ms 96492 KB Output is correct
4 Correct 9 ms 96492 KB Output is correct
5 Correct 7 ms 96492 KB Output is correct
6 Correct 6 ms 96492 KB Output is correct
7 Correct 10 ms 96492 KB Output is correct
8 Correct 4 ms 96492 KB Output is correct
9 Correct 6 ms 96492 KB Output is correct
10 Correct 13 ms 96492 KB Output is correct
11 Correct 6 ms 96492 KB Output is correct
12 Correct 10 ms 96492 KB Output is correct
13 Correct 6 ms 96492 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 97096 KB Output is correct
2 Correct 54 ms 97884 KB Output is correct
3 Correct 69 ms 98800 KB Output is correct
4 Correct 104 ms 99328 KB Output is correct
5 Correct 106 ms 99328 KB Output is correct
6 Correct 96 ms 99328 KB Output is correct
7 Correct 101 ms 99328 KB Output is correct
8 Correct 84 ms 99328 KB Output is correct
9 Correct 58 ms 99064 KB Output is correct
10 Correct 62 ms 99064 KB Output is correct
11 Correct 51 ms 98932 KB Output is correct
12 Correct 65 ms 99196 KB Output is correct
13 Correct 59 ms 99196 KB Output is correct
14 Correct 75 ms 99328 KB Output is correct
15 Correct 75 ms 99328 KB Output is correct
16 Correct 76 ms 99328 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 103932 KB Output is correct
2 Correct 283 ms 106276 KB Output is correct
3 Correct 374 ms 107860 KB Output is correct
4 Correct 586 ms 112944 KB Output is correct
5 Execution timed out 2000 ms 103668 KB Execution timed out
6 Halted 0 ms 0 KB -