oj.uz

Submission #137414

# Submission time Handle Problem Language Result Execution time Memory
137414 2019-07-27T17:07:08 Z MladenP Fortune Telling 2 (JOI14_fortune_telling2) C++17
4 / 100
 63 ms 3696 KB 
#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 200010
int N, K, a[MAXN], b[MAXN], t[MAXN];
int seg[4*MAXN];
void update(int node, int l, int r, int idx, int val) {
    if(l == r) {
        seg[node] = val;
        return;
    }
    if(idx <= mid) update(2*node, l, mid, idx, val);
    else update(2*node+1, mid+1, r, idx, val);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}
int query(int node, int l, int r, int L, int R) {
    if(r < l || R < L || r < L || R < l) return 0;
    if(L <= l && r <= R) return seg[node];
    int rez = 0;
    if(L <= mid) rez = max(rez, query(2*node, l, mid, L, R));
    if(R > mid) rez = max(rez, query(2*node+1, mid+1, r, L, R));
    return rez;
}
int bit[MAXN];
void update(int idx, int val) {
    while(idx < MAXN) {
        bit[idx] += val;
        idx += idx&-idx;
    }
}
int query(int idx) {
    int rez = 0;
    while(idx) {
        rez += bit[idx];
        idx -= idx&-idx;
    }
    return rez;
}
vector<pii> T, B;
int bsL(int key) {
    int l = 1, r = K, rez = K+1;
    while(l <= r) {
        if(T[mid].fi >= key) rez = mid, r = mid-1;
        else l = mid+1;
    }
    return rez;
}
int bsR(int key) {
    int l = 1, r = K, rez = 0;
    while(l <= r) {
        if(T[mid].fi <= key) rez = mid, l = mid+1;
        else r = mid-1;
    }
    return rez;
}
int sred[MAXN];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
    cin >> N >> K;
    for(int i = 1; i <= N; i++) cin >> a[i] >> b[i];
    for(int i = 1; i <= K; i++) cin >> t[i];
    T.pb({-INF, -INF}); B.pb({-INF, -INF});
    for(int i = 1; i <= N; i++) B.pb({max(a[i], b[i]), i});
    for(int i = 1; i <= K; i++) T.pb({t[i], i});
    sort(all(T));
    sort(all(B));
    for(int i = 1; i <= K; i++) {
        update(1, 1, K, i, T[i].se);
    }
    lld rez = 0;
    for(int i = 1; i <= N; i++) {
        int L = bsL(min(a[i], b[i])), R = bsR(max(a[i], b[i])-1);
        sred[i] = query(1, 1, K, L, R);
    }
    int cb = N, ct = K;
    while(cb > 0 || ct > 0) {
        int mode;
        if(cb == 0) mode = 0;
        else if(ct == 0) mode = 1;
        else mode = (B[cb] > T[ct]);
        if(mode == 0) {
            update(T[ct].se, +1);
            ct--;
        } else {
            int vece = (query(MAXN-1)-query(sred[B[cb].se]))%2;
            int idx = B[cb].se;
            if(sred[idx] == 0) {
                if(vece == 1) rez += b[idx];
                else rez += a[idx];
            } else {
                if(vece == 1) rez += min(a[idx], b[idx]);
                else rez += max(a[idx], b[idx]);
            }
            cb--;
        }
    }
    cout << rez;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 16 ms 1400 KB Output is correct
15 Correct 31 ms 2164 KB Output is correct
16 Correct 47 ms 2700 KB Output is correct
17 Correct 63 ms 3564 KB Output is correct
18 Correct 63 ms 3688 KB Output is correct
19 Correct 63 ms 3696 KB Output is correct
20 Correct 62 ms 3656 KB Output is correct
21 Correct 60 ms 3620 KB Output is correct
22 Correct 43 ms 3088 KB Output is correct
23 Correct 45 ms 3188 KB Output is correct
24 Correct 45 ms 3316 KB Output is correct
25 Correct 42 ms 3240 KB Output is correct
26 Correct 48 ms 3316 KB Output is correct
27 Correct 56 ms 3544 KB Output is correct
28 Correct 57 ms 3692 KB Output is correct
29 Incorrect 50 ms 3648 KB Output isn't correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 16 ms 1400 KB Output is correct
15 Correct 31 ms 2164 KB Output is correct
16 Correct 47 ms 2700 KB Output is correct
17 Correct 63 ms 3564 KB Output is correct
18 Correct 63 ms 3688 KB Output is correct
19 Correct 63 ms 3696 KB Output is correct
20 Correct 62 ms 3656 KB Output is correct
21 Correct 60 ms 3620 KB Output is correct
22 Correct 43 ms 3088 KB Output is correct
23 Correct 45 ms 3188 KB Output is correct
24 Correct 45 ms 3316 KB Output is correct
25 Correct 42 ms 3240 KB Output is correct
26 Correct 48 ms 3316 KB Output is correct
27 Correct 56 ms 3544 KB Output is correct
28 Correct 57 ms 3692 KB Output is correct
29 Incorrect 50 ms 3648 KB Output isn't correct