oj.uz

Submission #1100899

# Submission time Handle Problem Language Result Execution time Memory
1100899 2024-10-15T02:15:38 Z hahahoang132 Fortune Telling 2 (JOI14_fortune_telling2) C++17
4 / 100
 396 ms 46796 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)
{
    ll sz = (r - l + 1);
    ll tmp = 1;
    ll cnt = 0;
    while(tmp * 2 <= sz)
    {
        tmp *= 2;
        cnt++;
    }
    return max(sus[cnt][l],sus[cnt][r - tmp + 1]);
}
struct segtree
{
    ll n;
    ll b[N * 4];
    void build(ll n)
    {
        this->n = n;
    }
    void udt(ll x)
    {
        b[x]++;
    }
    ll get(ll l, ll r)
    {
        ll ans = 0;
        ll i,j;
        for(i = l;i <= r;i++) ans += b[i];
        return ans;
    }
};
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);
        //cout << haha[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(r == 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;
}

Compilation message

fortune_telling2.cpp: In member function 'long long int segtree::get(long long int, long long int)':
fortune_telling2.cpp:39:14: warning: unused variable 'j' [-Wunused-variable]
   39 |         ll i,j;
      |              ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41296 KB Output is correct
2 Correct 5 ms 41448 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 41400 KB Output is correct
7 Correct 6 ms 41724 KB Output is correct
8 Correct 5 ms 41552 KB Output is correct
9 Correct 6 ms 41428 KB Output is correct
10 Correct 6 ms 41552 KB Output is correct
11 Correct 8 ms 41552 KB Output is correct
12 Correct 6 ms 41552 KB Output is correct
13 Correct 6 ms 41552 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41296 KB Output is correct
2 Correct 5 ms 41448 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 41400 KB Output is correct
7 Correct 6 ms 41724 KB Output is correct
8 Correct 5 ms 41552 KB Output is correct
9 Correct 6 ms 41428 KB Output is correct
10 Correct 6 ms 41552 KB Output is correct
11 Correct 8 ms 41552 KB Output is correct
12 Correct 6 ms 41552 KB Output is correct
13 Correct 6 ms 41552 KB Output is correct
14 Correct 33 ms 43868 KB Output is correct
15 Correct 71 ms 44112 KB Output is correct
16 Correct 142 ms 44500 KB Output is correct
17 Correct 231 ms 44872 KB Output is correct
18 Correct 254 ms 44740 KB Output is correct
19 Correct 209 ms 44872 KB Output is correct
20 Correct 308 ms 44740 KB Output is correct
21 Correct 84 ms 44752 KB Output is correct
22 Correct 191 ms 44740 KB Output is correct
23 Correct 215 ms 44804 KB Output is correct
24 Correct 275 ms 44872 KB Output is correct
25 Correct 141 ms 44908 KB Output is correct
26 Correct 286 ms 46716 KB Output is correct
27 Correct 328 ms 46664 KB Output is correct
28 Correct 396 ms 46664 KB Output is correct
29 Incorrect 332 ms 46796 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41296 KB Output is correct
2 Correct 5 ms 41448 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 41400 KB Output is correct
7 Correct 6 ms 41724 KB Output is correct
8 Correct 5 ms 41552 KB Output is correct
9 Correct 6 ms 41428 KB Output is correct
10 Correct 6 ms 41552 KB Output is correct
11 Correct 8 ms 41552 KB Output is correct
12 Correct 6 ms 41552 KB Output is correct
13 Correct 6 ms 41552 KB Output is correct
14 Correct 33 ms 43868 KB Output is correct
15 Correct 71 ms 44112 KB Output is correct
16 Correct 142 ms 44500 KB Output is correct
17 Correct 231 ms 44872 KB Output is correct
18 Correct 254 ms 44740 KB Output is correct
19 Correct 209 ms 44872 KB Output is correct
20 Correct 308 ms 44740 KB Output is correct
21 Correct 84 ms 44752 KB Output is correct
22 Correct 191 ms 44740 KB Output is correct
23 Correct 215 ms 44804 KB Output is correct
24 Correct 275 ms 44872 KB Output is correct
25 Correct 141 ms 44908 KB Output is correct
26 Correct 286 ms 46716 KB Output is correct
27 Correct 328 ms 46664 KB Output is correct
28 Correct 396 ms 46664 KB Output is correct
29 Incorrect 332 ms 46796 KB Output isn't correct
30 Halted 0 ms 0 KB -