Submission #76469

#	Time	Username	Problem	Language	Result	Execution time	Memory
76469		win11905	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	35 / 100	3034 ms	94424 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<int> t[N<<1];
vector<pii> que;

int f(int m, int v) {
    int sum = 0;
    auto get = [&](int z) {
        int x = lower_bound(all(t[z]), v) - t[z].begin() - 1;
        sum += t[z].size() - x - 1;
    };
    for(int l = m + k, r = k + k; l < r; l >>= 1, r >>= 1) {
        if(l & 1) get(l++);
        if(r & 1) get(--r);
    }
    return sum;
}

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);
    }
    k++, t[k].emplace_back(0);
    for(int i = 1, ret; i < k; ++i) {
        scanf("%d", &ret);
        t[i+k].emplace_back(ret);
    }
    for(int i = k-1; i; --i) merge(all(t[i<<1]), all(t[i<<1|1]), back_inserter(t[i]));
    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;
        }
        long pa = ans;
        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:51:14: warning: unused variable 'pa' [-Wunused-variable]
         long pa = ans;
              ^~
fortune_telling2.cpp:32: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:34: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:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ret);
         ~~~~~^~~~~~~~~~~~

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