oj.uz

Submission #878363

# Submission time Handle Problem Language Result Execution time Memory
878363 2023-11-24T08:48:05 Z hafo Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 436 ms 71980 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 6e5 + 7;
const ll oo = 1e18 + 69;

int n, k, t[maxn], last[maxn];
pa a[maxn];
bool swapped[maxn];
vector<int> val, ev[2][maxn];

bool cmp(pa &a, pa &b) {
    return a.se < b.se;
} 

struct ST {
    struct node {
        int mx;
        friend node operator + (node a, const node &b) {
            maxi(a.mx, b.mx);
            return a;
        }
    };

    node st[4 * maxn];

    void update(int id, int l, int r, int pos, int val) {
        if(pos < l || pos > r) return;
        if(l == r) {
            maxi(st[id].mx, val);
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, pos, val);
        update(id << 1 | 1, mid + 1, r, pos, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    node get(int id, int l, int r, int u, int v) {
        if(r < u || l > v) return {0};
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    }


} st;

int id(int x) {
    return lower_bound(all(val), x) - val.begin() + 1;
}

struct BIT {
    int bit[maxn];

    void update(int x, int val) {
        for(; x <= k; x += x&-x) bit[x] += val;
    }
    
    int get(int x) {
        int ans = 0;
        for(; x; x -= x&-x) ans += bit[x];
        return ans;
    }

} bit;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>k;
    for(int i = 1; i <= n; i++) {
        cin>>a[i].fi>>a[i].se;
        val.pb(a[i].fi);
        val.pb(a[i].se);
        if(a[i].fi > a[i].se) {
            swap(a[i].fi, a[i].se);
            swapped[i] = 1;
        }
    }
    for(int i = 1; i <= k; i++) {
        cin>>t[i];
        val.pb(t[i]);
    }

    sort(all(val));
    val.erase(unique(all(val)), val.end());
    for(int i = 1; i <= k; i++) {
        int idd = id(t[i]);
        ev[0][idd].pb(i);
        st.update(1, 1, Size(val), idd, i);
    }
    for(int i = 1; i <= n; i++) {
        int l = id(a[i].fi);
        int r = id(a[i].se) - 1;
        if(l <= r) last[i] = st.get(1, 1, Size(val), l, r).mx;
        ev[1][r + 1].pb(i); 
    }

    ll ans = 0;
    for(int i = Size(val); i >= 1; i--) {
        for(auto j:ev[0][i]) bit.update(j, 1);
        for(auto j:ev[1][i]) {
            int cnt = bit.get(k) - bit.get(last[j]);
            if(last[j] != 0) swap(a[j].fi, a[j].se);
            if(cnt & 1) swap(a[j].fi, a[j].se);
            if(last[j] == 0 && swapped[j]) swap(a[j].fi, a[j].se);
            ans += a[j].fi;
        }
    }
    cout<<ans;
    return 0;
}

Compilation message

fortune_telling2.cpp: In member function 'void ST::update(int, int, int, int, int)':
fortune_telling2.cpp:48:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In member function 'ST::node ST::get(int, int, int, int, int)':
fortune_telling2.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35416 KB Output is correct
2 Correct 8 ms 35420 KB Output is correct
3 Correct 8 ms 35420 KB Output is correct
4 Correct 8 ms 35416 KB Output is correct
5 Correct 8 ms 35420 KB Output is correct
6 Correct 8 ms 35420 KB Output is correct
7 Correct 8 ms 35276 KB Output is correct
8 Correct 8 ms 35420 KB Output is correct
9 Correct 8 ms 35316 KB Output is correct
10 Correct 8 ms 35420 KB Output is correct
11 Correct 8 ms 35280 KB Output is correct
12 Correct 8 ms 35340 KB Output is correct
13 Correct 8 ms 35416 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35416 KB Output is correct
2 Correct 8 ms 35420 KB Output is correct
3 Correct 8 ms 35420 KB Output is correct
4 Correct 8 ms 35416 KB Output is correct
5 Correct 8 ms 35420 KB Output is correct
6 Correct 8 ms 35420 KB Output is correct
7 Correct 8 ms 35276 KB Output is correct
8 Correct 8 ms 35420 KB Output is correct
9 Correct 8 ms 35316 KB Output is correct
10 Correct 8 ms 35420 KB Output is correct
11 Correct 8 ms 35280 KB Output is correct
12 Correct 8 ms 35340 KB Output is correct
13 Correct 8 ms 35416 KB Output is correct
14 Correct 20 ms 36700 KB Output is correct
15 Correct 35 ms 37792 KB Output is correct
16 Correct 51 ms 41436 KB Output is correct
17 Correct 66 ms 42704 KB Output is correct
18 Correct 65 ms 42592 KB Output is correct
19 Correct 65 ms 42708 KB Output is correct
20 Correct 65 ms 42708 KB Output is correct
21 Correct 61 ms 42448 KB Output is correct
22 Correct 48 ms 41772 KB Output is correct
23 Correct 47 ms 41168 KB Output is correct
24 Correct 47 ms 41172 KB Output is correct
25 Correct 48 ms 41936 KB Output is correct
26 Correct 50 ms 42296 KB Output is correct
27 Correct 56 ms 42604 KB Output is correct
28 Correct 53 ms 42724 KB Output is correct
29 Correct 61 ms 42700 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35416 KB Output is correct
2 Correct 8 ms 35420 KB Output is correct
3 Correct 8 ms 35420 KB Output is correct
4 Correct 8 ms 35416 KB Output is correct
5 Correct 8 ms 35420 KB Output is correct
6 Correct 8 ms 35420 KB Output is correct
7 Correct 8 ms 35276 KB Output is correct
8 Correct 8 ms 35420 KB Output is correct
9 Correct 8 ms 35316 KB Output is correct
10 Correct 8 ms 35420 KB Output is correct
11 Correct 8 ms 35280 KB Output is correct
12 Correct 8 ms 35340 KB Output is correct
13 Correct 8 ms 35416 KB Output is correct
14 Correct 20 ms 36700 KB Output is correct
15 Correct 35 ms 37792 KB Output is correct
16 Correct 51 ms 41436 KB Output is correct
17 Correct 66 ms 42704 KB Output is correct
18 Correct 65 ms 42592 KB Output is correct
19 Correct 65 ms 42708 KB Output is correct
20 Correct 65 ms 42708 KB Output is correct
21 Correct 61 ms 42448 KB Output is correct
22 Correct 48 ms 41772 KB Output is correct
23 Correct 47 ms 41168 KB Output is correct
24 Correct 47 ms 41172 KB Output is correct
25 Correct 48 ms 41936 KB Output is correct
26 Correct 50 ms 42296 KB Output is correct
27 Correct 56 ms 42604 KB Output is correct
28 Correct 53 ms 42724 KB Output is correct
29 Correct 61 ms 42700 KB Output is correct
30 Correct 131 ms 49060 KB Output is correct
31 Correct 195 ms 55496 KB Output is correct
32 Correct 272 ms 59064 KB Output is correct
33 Correct 399 ms 70532 KB Output is correct
34 Correct 117 ms 48576 KB Output is correct
35 Correct 423 ms 71184 KB Output is correct
36 Correct 402 ms 70528 KB Output is correct
37 Correct 414 ms 71980 KB Output is correct
38 Correct 391 ms 71108 KB Output is correct
39 Correct 402 ms 70472 KB Output is correct
40 Correct 388 ms 70448 KB Output is correct
41 Correct 436 ms 71544 KB Output is correct
42 Correct 436 ms 70340 KB Output is correct
43 Correct 273 ms 66796 KB Output is correct
44 Correct 263 ms 66420 KB Output is correct
45 Correct 279 ms 66144 KB Output is correct
46 Correct 267 ms 59584 KB Output is correct
47 Correct 229 ms 61168 KB Output is correct
48 Correct 313 ms 67036 KB Output is correct
49 Correct 300 ms 67004 KB Output is correct