oj.uz

답안 #202514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202514 2020-02-16T18:54:05 Z dolphingarlic 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 7 ms 632 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

pair<int, int> a[200001];
int t[200001], segtree[2400001], bit[600001];
vector<pair<int, int>> c;
bool inv[200001], visited[200001];

void build(int node = 1, int l = 1, int r = c.size()) {
    if (l == r) segtree[node] = c[l - 1].second > 0 ? 0 : -c[l - 1].second;
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}

int rmq(int x, int y, int node = 1, int l = 1, int r = c.size()) {
    if (l > y || r < x) return 0;
    if (l >= x && r <= y) return segtree[node];
    int mid = (l + r) / 2;
    return max(rmq(x, y, node * 2, l, mid), rmq(x, y, node * 2 + 1, mid + 1, r));
}

void add(int pos) { for (; pos <= c.size(); pos += (pos & (-pos))) bit[pos]++; }

int rsq(int x, int y) {
    int ans = 0;
    for (; y; y -= (y & (-y))) ans += bit[y];
    for (x--; x; x -= (x & (-x))) ans -= bit[x];
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    FOR(i, 1, n + 1) {
        cin >> a[i].first >> a[i].second;
        inv[i] = a[i].first < a[i].second;
        if (inv[i]) swap(a[i].first, a[i].second);
        
        c.push_back({a[i].first, i});
        c.push_back({a[i].second, i});
    }
    FOR(i, 1, q + 1) {
        cin >> t[i];
        c.push_back({t[i], -i});
    }
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    build();

    FOR(i, 1, n + 1) {
        a[i].first = lower_bound(c.begin(), c.end(), make_pair(a[i].first, i)) - c.begin() + 1;
        a[i].second = lower_bound(c.begin(), c.end(), make_pair(a[i].second, -i)) - c.begin() + 1;
    }

    ll ans = 0;
    for (int i = c.size() - 1; i; i--) {
        int k = c[i].second;
        if (k > 0) {
            if (visited[k]) continue;
            visited[k] = true;

            int cnt = rsq(rmq(a[k].second, a[k].first), c.size());
            if (cnt & 1) ans += c[a[k].second - 1].first;
            else ans += c[a[k].first - 1].first;
        } else add(-k);
    }
    cout << ans;
    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'void add(int)':
fortune_telling2.cpp:28:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 void add(int pos) { for (; pos <= c.size(); pos += (pos & (-pos))) bit[pos]++; }
                            ~~~~^~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Runtime error 7 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Runtime error 7 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Runtime error 7 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -