oj.uz

답안 #152172

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152172 2019-09-06T16:52:16 Z karma 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 10 ms 6008 KB 
#include<bits/stdc++.h>
#define pb      emplace_back

using namespace std;

const int N = int(2e5) + 1;
const int M = int(6e5) + 1;

vector<int> v, c[N];
int n, m, a[N], b[N], t[N], p[N];
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 upper_bound(v.begin(), v.end(), x) - v.begin();}
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) {
       c[Query(1, Pos(min(a[i], b[i])), Pos(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(Pos(max(a[id], b[id])));
           if(i == 0 && a[i] < b[i]) ++h[id];
           if(h[id] & 1) res += min(a[id], b[id]);
           else res += max(a[id], b[id]);
       }
    }
    cout << res;
}

Compilation message

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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6008 KB Output is correct
2 Correct 8 ms 6008 KB Output is correct
3 Correct 10 ms 6008 KB Output is correct
4 Incorrect 9 ms 6008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6008 KB Output is correct
2 Correct 8 ms 6008 KB Output is correct
3 Correct 10 ms 6008 KB Output is correct
4 Incorrect 9 ms 6008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6008 KB Output is correct
2 Correct 8 ms 6008 KB Output is correct
3 Correct 10 ms 6008 KB Output is correct
4 Incorrect 9 ms 6008 KB Output isn't correct
5 Halted 0 ms 0 KB -