oj.uz

Submission #1100911

# Submission time Handle Problem Language Result Execution time Memory
1100911 2024-10-15T02:56:31 Z hahahoang132 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 316 ms 55740 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define bit(x,y) ((x >> y) & 1)
const ll N = 2e5 + 5;
const ll inf = LLONG_MAX/4;
pair<ll,ll> t[N];
ll a[N],b[N],sus[20][N],haha[N];
ll siu[N],id[N];
vector<ll> messi[N];
ll maxr(ll l, ll r)
{
    int p = __lg(r - l + 1);
    return max(sus[p][l],sus[p][r - (1 << p) + 1]);
}
struct segtree
{
    ll n;
    ll b[N * 4];
    void build(ll n)
    {
        this->n = n;
    }
    void udt(ll x)
    {
        udt(0,1,n,x);
    }
    void udt(ll x, ll l, ll r, ll u)
    {
        if(l == r)
        {
            b[x]++;
        }else
        {
            ll mid = (l + r) / 2;
            if(u <= mid) udt(x * 2 + 1,l,mid,u);
            else udt(x * 2 + 2,mid + 1,r,u);
            b[x] = b[x * 2 + 1] + b[x * 2 + 2];
        }
    }
    ll get(ll l, ll r)
    {
        return get(0,1,n,l,r);
    }
    ll get(ll x, ll l, ll r, ll s, ll e)
    {
        if(e < l || r < s) return 0;
        if(s <= l && r <= e) return b[x];
        ll mid = (l + r) / 2;
        return get(x * 2 + 1,l,mid,s,e) + get(x * 2 + 2,mid + 1,r,s,e);
    }
};
segtree f;
int main()
{
    ll n,q;
    cin >> n >> q;
    f.build(q);
    ll i,j;
    set<ll> tmp;
    for(i = 1;i <= n;i++)
    {
        cin >> a[i] >> b[i];
    }
    for(i = 1;i <= q;i++)
    {
        cin >> t[i].first;
        t[i].second = i;
    }
    sort(t + 1,t + 1 + q);
    for(i = 1;i <= q;i++)
    {
        id[t[i].second] = i;
        sus[0][i] = t[i].second;
    }
    for(i = 1;i < 20;i++)
    {
        for(j = 1;j <= q;j++)
        {
            sus[i][j] = max(sus[i - 1][j],sus[i - 1][j + (1 << (i - 1))]);
        }
    }
    for(i = 1;i <= n;i++)
    {
        ll s = min(a[i],b[i]);
        ll e = max(a[i],b[i]) - 1;
        if(s > t[q].first || t[1].first > e) continue;
        ll l = 1,r = q;
        ll k1,k2;
        while(true)
        {
            if(l == r)
            {
                k1 = l;
                break;
            }
            if(l + 1 == r)
            {
                if(t[l].first >= s) k1 = l;
                else k1 = r;
                break;
            }
            ll mid = (l + r) / 2;
            if(t[mid].first >= s) r = mid;
            else l = mid + 1;
        }
        l = 1;
        r = q;
        while(true)
        {
            if(l == r)
            {
                k2 = l;
                break;
            }
            if(l + 1 == r)
            {
                if(t[r].first <= e) k2 = r;
                else k2 = l;
                break;
            }
            ll mid = (l + r) / 2;
            if(t[mid].first <= e) l = mid;
            else r = mid - 1;
        }
        if(k1 > k2) haha[i] = 0;
        else haha[i] = maxr(k1,k2);
    }
    for(i = 1;i <= n;i++)
    {
        messi[haha[i]].push_back(i);
    }
    for(i = q;i >= 0;i--)
    {
        for(auto x : messi[i])
        {
            if(i > 0)
            {
                if(a[x] < b[x])
                {
                    siu[x] = 1;
                }
            }

            ll e = max(a[x],b[x]);
            ll l = 1,r = q + 1;
            ll k;
            while(true)
            {
                if(l == r)
                {
                    k = l;
                    break;
                }
                if(l + 1 == r)
                {
                    if(e <= t[l].first) k = l;
                    else k = r;
                    break;
                }
                ll mid = (l + r)/ 2;
                if(e <= t[mid].first) r = mid;
                else l = mid + 1;
            }
            if(k == q + 1) continue;
            siu[x] += f.get(k,q);
        }
        if(i > 0) f.udt(id[i]);
    }
    ll ans = 0;
    for(i = 1;i <= n;i++)
    {
        if(siu[i] % 2 == 0)
        {
            ans += a[i];
        }else
        {
            ans += b[i];
        }
    }
    cout << ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 41296 KB Output is correct
2 Correct 6 ms 41552 KB Output is correct
3 Correct 6 ms 41552 KB Output is correct
4 Correct 6 ms 41552 KB Output is correct
5 Correct 6 ms 41552 KB Output is correct
6 Correct 6 ms 41408 KB Output is correct
7 Correct 6 ms 41552 KB Output is correct
8 Correct 6 ms 41552 KB Output is correct
9 Correct 6 ms 41528 KB Output is correct
10 Correct 5 ms 41552 KB Output is correct
11 Correct 7 ms 41552 KB Output is correct
12 Correct 5 ms 41552 KB Output is correct
13 Correct 5 ms 41428 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 41296 KB Output is correct
2 Correct 6 ms 41552 KB Output is correct
3 Correct 6 ms 41552 KB Output is correct
4 Correct 6 ms 41552 KB Output is correct
5 Correct 6 ms 41552 KB Output is correct
6 Correct 6 ms 41408 KB Output is correct
7 Correct 6 ms 41552 KB Output is correct
8 Correct 6 ms 41552 KB Output is correct
9 Correct 6 ms 41528 KB Output is correct
10 Correct 5 ms 41552 KB Output is correct
11 Correct 7 ms 41552 KB Output is correct
12 Correct 5 ms 41552 KB Output is correct
13 Correct 5 ms 41428 KB Output is correct
14 Correct 17 ms 43856 KB Output is correct
15 Correct 29 ms 44668 KB Output is correct
16 Correct 42 ms 44616 KB Output is correct
17 Correct 56 ms 45640 KB Output is correct
18 Correct 56 ms 45504 KB Output is correct
19 Correct 55 ms 45652 KB Output is correct
20 Correct 55 ms 45640 KB Output is correct
21 Correct 52 ms 45504 KB Output is correct
22 Correct 37 ms 45684 KB Output is correct
23 Correct 41 ms 45384 KB Output is correct
24 Correct 37 ms 45648 KB Output is correct
25 Correct 37 ms 45648 KB Output is correct
26 Correct 48 ms 45384 KB Output is correct
27 Correct 51 ms 46800 KB Output is correct
28 Correct 52 ms 46664 KB Output is correct
29 Correct 62 ms 46788 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 41296 KB Output is correct
2 Correct 6 ms 41552 KB Output is correct
3 Correct 6 ms 41552 KB Output is correct
4 Correct 6 ms 41552 KB Output is correct
5 Correct 6 ms 41552 KB Output is correct
6 Correct 6 ms 41408 KB Output is correct
7 Correct 6 ms 41552 KB Output is correct
8 Correct 6 ms 41552 KB Output is correct
9 Correct 6 ms 41528 KB Output is correct
10 Correct 5 ms 41552 KB Output is correct
11 Correct 7 ms 41552 KB Output is correct
12 Correct 5 ms 41552 KB Output is correct
13 Correct 5 ms 41428 KB Output is correct
14 Correct 17 ms 43856 KB Output is correct
15 Correct 29 ms 44668 KB Output is correct
16 Correct 42 ms 44616 KB Output is correct
17 Correct 56 ms 45640 KB Output is correct
18 Correct 56 ms 45504 KB Output is correct
19 Correct 55 ms 45652 KB Output is correct
20 Correct 55 ms 45640 KB Output is correct
21 Correct 52 ms 45504 KB Output is correct
22 Correct 37 ms 45684 KB Output is correct
23 Correct 41 ms 45384 KB Output is correct
24 Correct 37 ms 45648 KB Output is correct
25 Correct 37 ms 45648 KB Output is correct
26 Correct 48 ms 45384 KB Output is correct
27 Correct 51 ms 46800 KB Output is correct
28 Correct 52 ms 46664 KB Output is correct
29 Correct 62 ms 46788 KB Output is correct
30 Correct 109 ms 53424 KB Output is correct
31 Correct 146 ms 53976 KB Output is correct
32 Correct 193 ms 54336 KB Output is correct
33 Correct 301 ms 55228 KB Output is correct
34 Correct 93 ms 53284 KB Output is correct
35 Correct 302 ms 55228 KB Output is correct
36 Correct 316 ms 55356 KB Output is correct
37 Correct 290 ms 55092 KB Output is correct
38 Correct 288 ms 55484 KB Output is correct
39 Correct 291 ms 55624 KB Output is correct
40 Correct 259 ms 55480 KB Output is correct
41 Correct 290 ms 55740 KB Output is correct
42 Correct 291 ms 55368 KB Output is correct
43 Correct 197 ms 55416 KB Output is correct
44 Correct 220 ms 55480 KB Output is correct
45 Correct 194 ms 55612 KB Output is correct
46 Correct 184 ms 55396 KB Output is correct
47 Correct 189 ms 55368 KB Output is correct
48 Correct 262 ms 55616 KB Output is correct
49 Correct 257 ms 55644 KB Output is correct