oj.uz

Submission #479453

# Submission time Handle Problem Language Result Execution time Memory
479453 2021-10-11T22:55:19 Z hidden1 Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 58208 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cerr << "Line: " << __LINE__ << endl; \
    prllDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void prllDebug(const char* name, T&& arg1) { cerr << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void prllDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cerr.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    prllDebug(end, args...);
}
 
const ll MAX_N = 6e5 + 10;
ll a[MAX_N], b[MAX_N];
ll n;
ll k;
ll t[MAX_N];

ll tree[4 * MAX_N];
ll treeUnder[MAX_N];
ll treeSum[4 * MAX_N];

void build(ll curr, ll l, ll r) {
    if(l == r) {
        tree[curr] = treeUnder[l];
        return;
    }
    ll m = (l + r) / 2ll;
    build(curr * 2, l, m);
    build(curr * 2 + 1, m + 1, r);
    tree[curr] = max(tree[curr * 2], tree[curr * 2 + 1]);
}

ll query(ll curr, ll l, ll r, ll ql, ll qr) {
    if(ql <= l && r <= qr) {
        return tree[curr];
    } else if(l > qr || r < ql) {return -1;}
    ll m = (l + r) / 2ll;
    return max(query(curr * 2, l, m, ql, qr), query(curr * 2 + 1, m + 1, r, ql, qr));
}

void updSum(ll curr, ll l, ll r, ll ind, ll val) {
    if(l == r && l == ind) {
        treeSum[curr] += val;
        return;
    } else if(ind < l || r < ind) {return;}
    ll m = (l + r) / 2ll;
    updSum(curr * 2, l, m, ind, val);
    updSum(curr * 2 + 1, m + 1, r, ind, val);
    treeSum[curr] = treeSum[curr * 2] + treeSum[curr * 2 + 1];    
}

ll querySum(ll curr, ll l, ll r, ll ql, ll qr) {
    if(ql <= l && r <= qr) {
        return treeSum[curr];
    } else if(l > qr || r < ql) {return 0;}
    ll m = (l + r) / 2ll;
    int ret = querySum(curr * 2, l, m, ql, qr) + querySum(curr * 2 + 1, m + 1, r, ql, qr);
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cerr.tie(NULL);
    fill(treeUnder, treeUnder + MAX_N, -1);
    fill(tree, tree + 4 * MAX_N, -1);

    cin >> n >> k;
    vector<ll> c;
    for(ll i = 0; i < n; i ++) {
        cin >> a[i] >> b[i];
        c.push_back(a[i]);
        c.push_back(b[i]);
    }
    for(ll i = 0; i < k; i ++) {
        cin >> t[i];
        c.push_back(t[i]);
    }
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    for(ll i = 0; i < n; i ++) {
        a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
        b[i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin();
    } 
    for(ll i = 0; i < k; i ++) {
        t[i] = lower_bound(c.begin(), c.end(), t[i]) - c.begin();
        treeUnder[t[i]] = i;
    } 

    build(1, 0, MAX_N - 1);

    vector<pair<ll, ll> > srt;
    vector<pair<ll, ll> > readyTo;
    for(ll i = 0; i < n; i ++) {
        srt.push_back({max(a[i], b[i]), i});
    }

    for(ll i = 0; i < k; i ++) {   
        readyTo.push_back({t[i], i});
    }

    sort(srt.rbegin(), srt.rend());
    sort(readyTo.rbegin(), readyTo.rend());

    ll ptr = 0, ret = 0;

    for(ll i = 0; i < n; i ++) {
        ll ind = srt[i].second;
        cerr << "Calculating " << c[a[ind]] << " " << c[b[ind]] << endl;

        while(ptr < k && srt[i].first <= readyTo[ptr].first) {
            updSum(1, 0, MAX_N - 1, readyTo[ptr].second, 1);
            cerr << "Adding " << readyTo[ptr].second << endl;
            ptr ++;
        }

        if(a[ind] == b[ind]) {
            ret += c[a[ind]];
            continue;
        }

        ll mn = min(a[ind], b[ind]), mx = max(a[ind], b[ind]);
        ll l = query(1, 0, MAX_N - 1, mn, mx - 1);
        ll cnt = querySum(1, 0, MAX_N - 1, l + 1, MAX_N - 1);

        if(l == -1) {
            if(cnt & 1) {
                ret += c[b[ind]];
            } else {                
                ret += c[a[ind]];
            }
        } else {
            if(cnt & 1) {
                ret += c[mn];
            } else {             
                ret += c[mx];
            }            
        }

        cerr << mn << " " << mx << " | " << " " << l << " " << cnt << " " << ret << endl;
    }

    cout << ret << endl;

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23884 KB Output is correct
2 Correct 31 ms 24012 KB Output is correct
3 Correct 40 ms 24064 KB Output is correct
4 Correct 44 ms 24024 KB Output is correct
5 Correct 41 ms 23968 KB Output is correct
6 Correct 39 ms 24032 KB Output is correct
7 Correct 40 ms 24012 KB Output is correct
8 Correct 37 ms 24012 KB Output is correct
9 Correct 36 ms 23884 KB Output is correct
10 Correct 42 ms 24036 KB Output is correct
11 Correct 43 ms 24156 KB Output is correct
12 Correct 40 ms 24132 KB Output is correct
13 Correct 40 ms 24012 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23884 KB Output is correct
2 Correct 31 ms 24012 KB Output is correct
3 Correct 40 ms 24064 KB Output is correct
4 Correct 44 ms 24024 KB Output is correct
5 Correct 41 ms 23968 KB Output is correct
6 Correct 39 ms 24032 KB Output is correct
7 Correct 40 ms 24012 KB Output is correct
8 Correct 37 ms 24012 KB Output is correct
9 Correct 36 ms 23884 KB Output is correct
10 Correct 42 ms 24036 KB Output is correct
11 Correct 43 ms 24156 KB Output is correct
12 Correct 40 ms 24132 KB Output is correct
13 Correct 40 ms 24012 KB Output is correct
14 Correct 280 ms 25832 KB Output is correct
15 Correct 584 ms 27740 KB Output is correct
16 Correct 822 ms 30228 KB Output is correct
17 Correct 1074 ms 32816 KB Output is correct
18 Correct 1078 ms 32628 KB Output is correct
19 Correct 1035 ms 32536 KB Output is correct
20 Correct 1136 ms 32816 KB Output is correct
21 Correct 937 ms 32304 KB Output is correct
22 Correct 954 ms 31584 KB Output is correct
23 Correct 986 ms 31664 KB Output is correct
24 Correct 1065 ms 31588 KB Output is correct
25 Correct 947 ms 31492 KB Output is correct
26 Correct 923 ms 32080 KB Output is correct
27 Correct 1047 ms 32772 KB Output is correct
28 Correct 1022 ms 32684 KB Output is correct
29 Correct 1043 ms 32832 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23884 KB Output is correct
2 Correct 31 ms 24012 KB Output is correct
3 Correct 40 ms 24064 KB Output is correct
4 Correct 44 ms 24024 KB Output is correct
5 Correct 41 ms 23968 KB Output is correct
6 Correct 39 ms 24032 KB Output is correct
7 Correct 40 ms 24012 KB Output is correct
8 Correct 37 ms 24012 KB Output is correct
9 Correct 36 ms 23884 KB Output is correct
10 Correct 42 ms 24036 KB Output is correct
11 Correct 43 ms 24156 KB Output is correct
12 Correct 40 ms 24132 KB Output is correct
13 Correct 40 ms 24012 KB Output is correct
14 Correct 280 ms 25832 KB Output is correct
15 Correct 584 ms 27740 KB Output is correct
16 Correct 822 ms 30228 KB Output is correct
17 Correct 1074 ms 32816 KB Output is correct
18 Correct 1078 ms 32628 KB Output is correct
19 Correct 1035 ms 32536 KB Output is correct
20 Correct 1136 ms 32816 KB Output is correct
21 Correct 937 ms 32304 KB Output is correct
22 Correct 954 ms 31584 KB Output is correct
23 Correct 986 ms 31664 KB Output is correct
24 Correct 1065 ms 31588 KB Output is correct
25 Correct 947 ms 31492 KB Output is correct
26 Correct 923 ms 32080 KB Output is correct
27 Correct 1047 ms 32772 KB Output is correct
28 Correct 1022 ms 32684 KB Output is correct
29 Correct 1043 ms 32832 KB Output is correct
30 Correct 1162 ms 43588 KB Output is correct
31 Correct 2033 ms 51500 KB Output is correct
32 Execution timed out 3084 ms 58208 KB Time limit exceeded
33 Halted 0 ms 0 KB -