oj.uz

답안 #52210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52210 2018-06-25T04:58:09 Z 강태규(#1345) 운세 보기 2 (JOI14_fortune_telling2) C++11
0 / 100
 4 ms 2424 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

struct card {
    int a, b, t;
    void scan() {
        scanf("%d%d", &a, &b);
        if (a > b) swap(a, b), t = 1;
        else t = 0;
    }
    bool operator<(const card &c) const {
        return a < c.a;
    }
};

const int MAXN = 2e5 + 1;
int n, k;
card cs[MAXN];
int t[MAXN];
pii ct[MAXN];
int segm[1 << 19];
int segs[1 << 19];

int queryMax(int i, int s, int e, int x) {
    if (x <= segm[i]) return 0;
    if (s == e) return s;
    int m = (s + e) / 2;
    int ret = queryMax(i << 1 | 1, m + 1, e, x);
    if (ret) return ret;
    return queryMax(i << 1, s, m, x);
}

void update(int i, int s, int e, int x, int v) {
    if (s == e) {
        segm[i] = v;
        ++segs[i];
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(i << 1, s, m, x, v);
    else update(i << 1 | 1, m + 1, e, x, v);
    segm[i] = min(segm[i << 1], segm[i << 1 | 1]);
    segs[i] = segs[i << 1] + segs[i << 1 | 1];
}

int querySum(int i, int s, int e, int x, int y) {
    if (e < x || y < s) return 0;
    if (x <= s && e <= y) return segs[i];
    int m = (s + e) / 2;
    return querySum(i << 1, s, m, x, y) + querySum(i << 1 | 1, m + 1, e, x, y);
}

const int inf = 1e9 + 7;
int main() {
    for (int i = 0; i < (1 << 19); ++i) segm[i] = inf;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        cs[i].scan();
    }
    for (int i = 1; i <= k; ++i) {
        scanf("%d", t + i);
        ct[i - 1] = { t[i], i };
    }
    sort(cs, cs + n);
    sort(ct, ct + k, greater<pii>());
    llong ans = 0;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < k && cs[i].a <= ct[j].first) {
            update(1, 1, k, ct[j].second, ct[j].first);
            ++j;
        }
        int x = queryMax(1, 1, k, cs[i].b);
        if (x) cs[i].t = 1;
        int cnt = querySum(1, 1, k, x + 1, k) % 2;
        if (cnt ^ cs[i].t) ans += cs[i].b;
        else ans += cs[i].a;
    }
    printf("%lld\n", ans);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:73: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:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", t + i);
         ~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp: In member function 'void card::scan()':
fortune_telling2.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -