Submission #152181

#	Time	Username	Problem	Language	Result	Execution time	Memory
152181		karma	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	585 ms	44360 KiB

fortune_telling2

#include<bits/stdc++.h>
#define pb      emplace_back

using namespace std;

const int N = int(2e5) + 5;
const int M = N * 3;

vector<int> v, c[N];
int n, m, a[N], b[N], t[N], p[M];
int l[M << 2], h[M << 2], st[M << 2];

void Build(int x, int low, int high) {
     l[x] = low, h[x] = high;
     if(l[x] == h[x]) {
        st[x] = p[l[x]];
        return;
     }
     int mid = (low + high) >> 1;
     Build(x << 1, low, mid);
     Build(x << 1 | 1, mid + 1, high);
     st[x] = max(st[x << 1], st[x << 1 | 1]);
}

int Query(int x, int low, int high) {
    if(high < low) return -1;
    if(l[x] > high || h[x] < low) return -1;
    if(l[x] >= low && h[x] <= high) return st[x];
    return max(Query(x << 1, low, high), Query(x << 1 | 1, low, high));
}

int Pos(int x) {return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;}
void Update(int x) {
    for(; x > 0; x -= (x & -x)) ++l[x];
}
int Get(int x) {
    int res = 0;
    for(; x <= int(v.size()); x += (x & -x)) res += l[x];
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        v.pb(a[i]), v.pb(b[i]);
    }
    for(int i = 0; i < m; ++i) cin >> t[i], v.pb(t[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    memset(&p, -1, sizeof p);
    for(int i = 0; i < m; ++i) p[t[i] = Pos(t[i])] = i;
    Build(1, 1, int(v.size()));
    for(int i = 0; i < n; ++i) {
       a[i] = Pos(a[i]), b[i] = Pos(b[i]);
       c[Query(1, min(a[i], b[i]), max(a[i], b[i]) - 1) + 1].pb(i);
    }
    fill(l, l + int(v.size()) + 1, 0);
    long long res = 0;
    for(int i = m; i >= 0; --i) {
       if(i - m) Update(t[i]);
       for(int id: c[i]) {
           h[id] = Get(max(a[id], b[id]));
           if(i == 0 && a[id] < b[id]) ++h[id];
           if(h[id] & 1) res += v[min(a[id], b[id]) - 1];
           else res += v[max(a[id], b[id]) - 1];
       }
    }
    cout << res;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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