oj.uz

Submission #791362

# Submission time Handle Problem Language Result Execution time Memory
791362 2023-07-24T03:56:15 Z Cookie Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 72 ms 18820 KB 
#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 6e5, base = 74;
const ll p = 31, mod = 1e9 + 7;
int n, k;
int st[4 * mxn + 1], bit[mxn + 1];
void upd(int nd, int l, int r, int id, int v){
    if(id < l || id > r)return;
    if(l == r){
        st[nd] = max(st[nd], v);
        return;
    }
    int mid = (l + r) >> 1;
    upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
    st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
}
int get(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(0);
    if(ql <= l && qr >= r)return(st[nd]);
    int mid = (l + r) >> 1;
    return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
vt<int>comp;
void updbit(int p, int v){
    while(p <= sz(comp)){
        bit[p] += v; p += p & (-p);
    }
}
int getbit(int p){
    int ans = 0;
    while(p){
        ans += bit[p]; p -= p & (-p);
    }
    return(ans);
}
int find(int x){
    return(lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1);
}
vt<int>q[mxn + 1];
ll a[mxn + 1], b[mxn + 1], c[mxn + 1];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i]; comp.pb(a[i]); comp.pb(b[i]);
    }
    for(int i = 1; i <= k; i++){
        cin >> c[i]; comp.pb(c[i]);
    }
    sort(comp.begin(), comp.end());
    for(int i = 1; i <= k; i++){
        upd(1, 1, sz(comp), find(c[i]), i);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        int mn = find(min(a[i], b[i])), mx = find(max(a[i], b[i]));
        if(mn == mx){
            ans += comp[mn - 1];
            continue;
        }
        int mxid = get(1, 1, sz(comp), mn, mx - 1);
        //cout << i << " " << mxid << "\n";
        q[mxid].pb(i);
    }
    for(int i = k; i >= 1; i--){
        for(auto j: q[i]){
            int mx = find(max(a[j], b[j]));
            ll turn = getbit(sz(comp)) - getbit(mx - 1);
            //cout << i << " " << j << " " << turn << "\n";
            if(turn & 1){
                ans += min(a[j], b[j]);
            }else{
                ans += max(a[j], b[j]);
            }
        }
        updbit(find(c[i]), 1);
    }
    for(auto i: q[0]){
        int mx = find(max(a[i], b[i]));
        int turn = getbit(sz(comp)) - getbit(mx);
        if(turn % 2 == 0)ans += a[i];
        else ans += b[i];
    }
    cout << ans;
    return(0);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14436 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 8 ms 14572 KB Output is correct
6 Correct 8 ms 14480 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 7 ms 14548 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 8 ms 14472 KB Output is correct
11 Correct 8 ms 14580 KB Output is correct
12 Correct 7 ms 14460 KB Output is correct
13 Correct 8 ms 14564 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14436 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 8 ms 14572 KB Output is correct
6 Correct 8 ms 14480 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 7 ms 14548 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 8 ms 14472 KB Output is correct
11 Correct 8 ms 14580 KB Output is correct
12 Correct 7 ms 14460 KB Output is correct
13 Correct 8 ms 14564 KB Output is correct
14 Correct 21 ms 15472 KB Output is correct
15 Correct 33 ms 16616 KB Output is correct
16 Correct 47 ms 17916 KB Output is correct
17 Correct 63 ms 18704 KB Output is correct
18 Correct 62 ms 18764 KB Output is correct
19 Correct 63 ms 18700 KB Output is correct
20 Correct 72 ms 18688 KB Output is correct
21 Correct 62 ms 18792 KB Output is correct
22 Correct 48 ms 18252 KB Output is correct
23 Correct 49 ms 18220 KB Output is correct
24 Correct 57 ms 18248 KB Output is correct
25 Correct 48 ms 18408 KB Output is correct
26 Correct 48 ms 18092 KB Output is correct
27 Correct 60 ms 18680 KB Output is correct
28 Correct 51 ms 18316 KB Output is correct
29 Incorrect 61 ms 18820 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14436 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 8 ms 14572 KB Output is correct
6 Correct 8 ms 14480 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 7 ms 14548 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 8 ms 14472 KB Output is correct
11 Correct 8 ms 14580 KB Output is correct
12 Correct 7 ms 14460 KB Output is correct
13 Correct 8 ms 14564 KB Output is correct
14 Correct 21 ms 15472 KB Output is correct
15 Correct 33 ms 16616 KB Output is correct
16 Correct 47 ms 17916 KB Output is correct
17 Correct 63 ms 18704 KB Output is correct
18 Correct 62 ms 18764 KB Output is correct
19 Correct 63 ms 18700 KB Output is correct
20 Correct 72 ms 18688 KB Output is correct
21 Correct 62 ms 18792 KB Output is correct
22 Correct 48 ms 18252 KB Output is correct
23 Correct 49 ms 18220 KB Output is correct
24 Correct 57 ms 18248 KB Output is correct
25 Correct 48 ms 18408 KB Output is correct
26 Correct 48 ms 18092 KB Output is correct
27 Correct 60 ms 18680 KB Output is correct
28 Correct 51 ms 18316 KB Output is correct
29 Incorrect 61 ms 18820 KB Output isn't correct
30 Halted 0 ms 0 KB -