oj.uz

Submission #1100909

# Submission time Handle Problem Language Result Execution time Memory
1100909 2024-10-15T02:53:14 Z hahahoang132 Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 3000 ms 51832 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)
    {
        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);
    }
    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;
}

Compilation message

fortune_telling2.cpp: In member function 'long long int segtree::get(long long int, long long int)':
fortune_telling2.cpp:32:14: warning: unused variable 'j' [-Wunused-variable]
   32 |         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 6 ms 41552 KB Output is correct
3 Correct 7 ms 41552 KB Output is correct
4 Correct 7 ms 41720 KB Output is correct
5 Correct 7 ms 41552 KB Output is correct
6 Correct 6 ms 41720 KB Output is correct
7 Correct 7 ms 41720 KB Output is correct
8 Correct 6 ms 41552 KB Output is correct
9 Correct 6 ms 41552 KB Output is correct
10 Correct 6 ms 41552 KB Output is correct
11 Correct 6 ms 41404 KB Output is correct
12 Correct 7 ms 41552 KB Output is correct
13 Correct 6 ms 41444 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41296 KB Output is correct
2 Correct 6 ms 41552 KB Output is correct
3 Correct 7 ms 41552 KB Output is correct
4 Correct 7 ms 41720 KB Output is correct
5 Correct 7 ms 41552 KB Output is correct
6 Correct 6 ms 41720 KB Output is correct
7 Correct 7 ms 41720 KB Output is correct
8 Correct 6 ms 41552 KB Output is correct
9 Correct 6 ms 41552 KB Output is correct
10 Correct 6 ms 41552 KB Output is correct
11 Correct 6 ms 41404 KB Output is correct
12 Correct 7 ms 41552 KB Output is correct
13 Correct 6 ms 41444 KB Output is correct
14 Correct 36 ms 44024 KB Output is correct
15 Correct 74 ms 44112 KB Output is correct
16 Correct 149 ms 44360 KB Output is correct
17 Correct 230 ms 44756 KB Output is correct
18 Correct 253 ms 44740 KB Output is correct
19 Correct 224 ms 44748 KB Output is correct
20 Correct 306 ms 44744 KB Output is correct
21 Correct 81 ms 44740 KB Output is correct
22 Correct 176 ms 44872 KB Output is correct
23 Correct 216 ms 44616 KB Output is correct
24 Correct 273 ms 44932 KB Output is correct
25 Correct 139 ms 44748 KB Output is correct
26 Correct 280 ms 46704 KB Output is correct
27 Correct 321 ms 46664 KB Output is correct
28 Correct 404 ms 46836 KB Output is correct
29 Correct 342 ms 46788 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41296 KB Output is correct
2 Correct 6 ms 41552 KB Output is correct
3 Correct 7 ms 41552 KB Output is correct
4 Correct 7 ms 41720 KB Output is correct
5 Correct 7 ms 41552 KB Output is correct
6 Correct 6 ms 41720 KB Output is correct
7 Correct 7 ms 41720 KB Output is correct
8 Correct 6 ms 41552 KB Output is correct
9 Correct 6 ms 41552 KB Output is correct
10 Correct 6 ms 41552 KB Output is correct
11 Correct 6 ms 41404 KB Output is correct
12 Correct 7 ms 41552 KB Output is correct
13 Correct 6 ms 41444 KB Output is correct
14 Correct 36 ms 44024 KB Output is correct
15 Correct 74 ms 44112 KB Output is correct
16 Correct 149 ms 44360 KB Output is correct
17 Correct 230 ms 44756 KB Output is correct
18 Correct 253 ms 44740 KB Output is correct
19 Correct 224 ms 44748 KB Output is correct
20 Correct 306 ms 44744 KB Output is correct
21 Correct 81 ms 44740 KB Output is correct
22 Correct 176 ms 44872 KB Output is correct
23 Correct 216 ms 44616 KB Output is correct
24 Correct 273 ms 44932 KB Output is correct
25 Correct 139 ms 44748 KB Output is correct
26 Correct 280 ms 46704 KB Output is correct
27 Correct 321 ms 46664 KB Output is correct
28 Correct 404 ms 46836 KB Output is correct
29 Correct 342 ms 46788 KB Output is correct
30 Correct 348 ms 51016 KB Output is correct
31 Correct 1406 ms 51424 KB Output is correct
32 Correct 2670 ms 51832 KB Output is correct
33 Execution timed out 3060 ms 51544 KB Time limit exceeded
34 Halted 0 ms 0 KB -