Submission #76477

#	Time	Username	Problem	Language	Result	Execution time	Memory
76477		win11905	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	2814 ms	139760 KiB

fortune_telling2

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

#define all(x) x.begin(), x.end()
#define long long long
#define pii pair<int, int>
#define x first
#define y second

const int N = 2e5+5;

int n, k;
long ans;
vector<pii> que;
vector<int> coor;

struct item {
    int v;
    item *l, *r;
    item() {}
    item(int v, item *l, item *r) : v(v), l(l), r(r) {}
};

using pitem = item*;

#define vari pitem p, int l = 0, int r = coor.size()
#define mid ((l + r) >> 1)
#define lb p->l, l, mid
#define rb p->r, mid+1, r

pitem newleaf(int v) { return new item(v, nullptr, nullptr); } 

pitem newpar(pitem l, pitem r) { return new item(l->v + r->v, l, r); }

pitem build(int l = 0, int r = coor.size()) {
    if(l == r) return newleaf(0);
    return newpar(build(l, mid), build(mid+1, r));
}

pitem update(int x, vari) {
    if(l == r) return newleaf(p->v + 1);
    if(x <= mid) return newpar(update(x, lb), p->r);
    else return newpar(p->l, update(x, rb));
}

int query(int x, vari) {
    if(x <= l) return p->v;
    if(x > mid) return query(x, rb);
    return query(x, lb) + query(x, rb); 
}

int A[N];
pitem ver[N];

int f(int m, int v) {
    return query(lower_bound(all(coor), v) - coor.begin(), ver[m]);
}

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0, a, b; i < n; ++i) {
        scanf("%d %d", &a, &b);
        que.emplace_back(a, b);
    }
    coor.resize(1);
    for(int i = 1; i <= k; ++i) {
        scanf("%d", A+i);
        coor.emplace_back(A[i]);
    }
    sort(all(coor));
    coor.resize(unique(all(coor)) - coor.begin());
    ver[k+1] = build();
    for(int i = k; ~i; --i) ver[i] = update(lower_bound(all(coor), A[i]) - coor.begin(), ver[i+1]);
    for(auto x : que) {
        int a, b; tie(a, b) = x;
        int l = 0, r = k;
        while(l < r) {
            int m = (l + r + 1) >> 1;
            if(f(m, a) != f(m, b)) l = m;
            else r = m-1;
        }
        if(l == 0) ans += f(0, a) & 1 ? b : a;
        else ans += f(l, max(a, b)) & 1 ? min(a, b) : max(a, b);
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+i);
         ~~~~~^~~~~~~~~~~

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