Submission #370300

#	Time	Username	Problem	Language	Result	Execution time	Memory
370300		parsabahrami	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	766 ms	80504 KiB

fortune_telling2

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 1e6 + 10;
int F[N], seg[N << 2], M[N], A[N], B[N], C[N], n, q;
vector<int> cp, vec[2][N];

void modify(int p, int x, int id = 1, int l = 0, int r = SZ(cp)) {
    if (r - l < 2) {
        seg[id] = max(seg[id], x);
        return;
    }
    int mid = (l + r) >> 1;
    if (p < mid) modify(p, x, lc, l, mid);
    else modify(p, x, rc, mid, r);
    seg[id] = max(seg[lc], seg[rc]);
}

int get(int ql, int qr, int id = 1, int l = 0, int r = SZ(cp)) {
    if (qr <= l || r <= ql) return 0;
    if (ql <= l && r <= qr) return seg[id];
    int mid = (l + r) >> 1;
    return max(get(ql, qr, lc, l, mid), get(ql, qr, rc, mid, r));
}

int id(int x) {
    return lower_bound(cp.begin(), cp.end(), x) - cp.begin();
}

int get(int p) {
    int ret = 0;
    for (p++; p; p -= p & -p) 
        ret += F[p];
    return ret;
}

void upd(int p, int x) {
    for (p++; p < N; p += p & -p) 
        F[p] += x;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) 
        scanf("%d%d", &A[i], &B[i]), cp.push_back(A[i]), cp.push_back(B[i]);
    for (int i = 1; i <= q; i++) 
        scanf("%d", &C[i]), cp.push_back(C[i]);
    sort(cp.begin(), cp.end());
    cp.resize(unique(cp.begin(), cp.end()) - cp.begin());
    for (int i = 1; i <= q; i++) 
        modify(id(C[i]), i);
    for (int i = 1; i <= n; i++) {
        M[i] = get(id(min(A[i], B[i])), id(max(A[i], B[i])));
    }
    for (int i = 1; i <= n; i++) {
        vec[0][id(max(A[i], B[i]))].push_back(i);
    }
    ll tot = 0;
    for (int i = 1; i <= q; i++) 
        vec[1][id(C[i])].push_back(i);
    for (int i = SZ(cp) - 1; ~i; i--) {
        for (int j : vec[1][i]) upd(j, 1);
        for (int j : vec[0][i]) {
            int x = get(N - 2) - get(M[j]);
            if (!M[j]) {
                tot += (x & 1 ? B[j] : A[j]);
            } else {
                if (A[j] > B[j]) swap(A[j], B[j]);
                tot += (x & 1 ? A[j] : B[j]);
            }
        }
    }
    printf("%lld\n", tot);
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |         scanf("%d%d", &A[i], &B[i]), cp.push_back(A[i]), cp.push_back(B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         scanf("%d", &C[i]), cp.push_back(C[i]);
      |         ~~~~~^~~~~~~~~~~~~

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