Submission #773385

#	Time	Username	Problem	Language	Result	Execution time	Memory
773385		Kubogi	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	379 ms	44572 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)

const int maxn = 2e5+4, inf = 1e18;
int n, q, a[maxn], b[maxn], t[maxn];

int ac[maxn], bc[maxn], tc[maxn];
int compress(int &x, vector<int> &v) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int st[maxn*12];
void update(int id, int l, int r, int i, int v) {
    if (i < l || i > r) return;
    if (l == r) {
        st[id] = max(st[id], v);
        return;
    }

    int mid = (l+r)>>1;
    update(id*2, l, mid, i, v);
    update(id*2+1, mid+1, r, i, v);

    st[id] = max(st[id*2], st[id*2+1]);
}

int get(int id, int l, int r, int a, int b) {
    if (r < a || b < l) return -inf;
    if (a <= l && r <= b) {
        return st[id];
    }

    int mid = (l+r)>>1;
    return max(get(id*2, l, mid, a, b), get(id*2+1, mid+1, r, a, b));
}

int bit[maxn*3];
void add(int i, int v) {
    while (i <= n*2+q) {
        bit[i] += v;
        i += (i & (-i));
    }
}
int qq(int i) {
    int res = 0;
    while (i > 0) {
        res += bit[i];
        i -= (i & (-i));
    }
    return res;
}
int getr(int l, int r) {
    return qq(r) - qq(l-1);
}

struct query {
    int idx, x;

    bool operator <(const query &A) const {
        return x > A.x;
    }
} Q[maxn];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fileio("");
    // freopen("debug.txt", "w", stderr);

    cin >> n >> q;
    vector<int> sech;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        sech.push_back(a[i]);
        sech.push_back(b[i]);
    }
    for (int i = 1; i <= q; i++) {
        cin >> t[i];
        sech.push_back(t[i]);
    }
    sort(sech.begin(), sech.end());

    for (int i = 1; i <= n; i++) {
        ac[i] = compress(a[i], sech);
        bc[i] = compress(b[i], sech);
    }
    for (int i = 1; i <= q; i++) {
        tc[i] = compress(t[i], sech);
        update(1, 1, n*2+q, tc[i], i);
    }

    for (int i = 1; i <= n; i++) {
        Q[i] = {i, get(1, 1, n*2+q, min(ac[i], bc[i]), max(ac[i], bc[i])-1)};
    }
    sort(Q+1, Q+1+n);

    int j = q, res = 0;
    for (int i = 1; i <= n; i++) {
        while (j > 0 && j > Q[i].x) {
            add(tc[j], 1);
            j--;
        }

        int id = Q[i].idx;
        if (Q[i].x > 0) {
            int p = (1 + getr(max(ac[id], bc[id]), n*2+q)) % 2;
            int y[2] = {min(a[id], b[id]), max(a[id], b[id])};
            res += y[p];
        } else {
            int p = getr(max(ac[id], bc[id]), n*2+q) % 2;
            int y[2] = {a[id], b[id]};
            res += y[p];
        }
    }
    cout << res;

    return 0 ^ 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:70:5: note: in expansion of macro 'fileio'
   70 |     fileio("");
      |     ^~~~~~
fortune_telling2.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:70:5: note: in expansion of macro 'fileio'
   70 |     fileio("");
      |     ^~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65