oj.uz

Submission #888885

# Submission time Handle Problem Language Result Execution time Memory
888885 2023-12-18T10:33:23 Z 12345678 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 334 ms 23752 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;
int n, k, a[nx], b[nx], t[nx], l[nx], sw[nx], cnt[nx];
long long res;
vector<int> v, d[nx];

struct segtree
{
    int d[4*nx];
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=max(d[i], vl));
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (ql<=l&&r<=qr) return d[i];
        if (qr<l||r<ql) return 0;
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

struct segtreesum
{
    int d[4*nx];
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]+=vl);
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (ql<=l&&r<=qr) return d[i];
        if (qr<l||r<ql) return 0;
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} ss;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>a[i]>>b[i];
    for (int i=1; i<=n; i++) if (a[i]>b[i]) swap(a[i], b[i]), sw[i]=1;
    for (int i=1; i<=k; i++) cin>>t[i], v.push_back(t[i]);
    sort(v.begin(), v.end());
    for (int i=1; i<=k; i++) s.update(1, k, 1, lower_bound(v.begin(), v.end(), t[i])-v.begin()+1, i);
    for (int i=1; i<=n; i++)
    {
        int ql=lower_bound(v.begin(), v.end(), a[i])-v.begin()+1;
        int qr=upper_bound(v.begin(), v.end(), b[i]-1)-v.begin();
        if (ql>k||qr<1||qr<ql) continue;
        l[i]=s.query(1, k, 1, ql, qr);
    }
    for (int i=1; i<=n; i++) d[l[i]].push_back(i);
    for (int i=k; i>=0; i--)
    {
        for (auto x:d[i])
        {
            int qr=lower_bound(v.begin(), v.end(), b[x])-v.begin()+1, tmp;
            if (qr>k) tmp=0;
            else tmp=ss.query(1, k, 1, qr, k);
            if (i!=0&&tmp%2==0) res+=b[x];
            else if (i!=0) res+=a[x];
            else if (tmp%2==0&&sw[x]==0) res+=a[x];
            else if (tmp%2==0&&sw[x]) res+=b[x];
            else if (tmp%2==1&&sw[x]==0) res+=b[x];
            else res+=a[x];
            //cout<<x<<' '<<tmp<<' '<<qr<<' '<<res<<'\n';
        }
        if (i!=0) ss.update(1, k, 1, lower_bound(v.begin(), v.end(), t[i])-v.begin()+1, 1);
    }
    cout<<res;
}

/*
5 5
1 2
2 3
3 2
2 1
1 1
10
10
10
10
10
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 3 ms 10744 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 3 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 3 ms 10588 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 3 ms 10744 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 3 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 3 ms 10588 KB Output is correct
14 Correct 14 ms 11308 KB Output is correct
15 Correct 27 ms 12112 KB Output is correct
16 Correct 40 ms 12480 KB Output is correct
17 Correct 54 ms 13368 KB Output is correct
18 Correct 67 ms 13268 KB Output is correct
19 Correct 54 ms 13272 KB Output is correct
20 Correct 53 ms 13360 KB Output is correct
21 Correct 52 ms 13392 KB Output is correct
22 Correct 44 ms 12756 KB Output is correct
23 Correct 40 ms 13012 KB Output is correct
24 Correct 40 ms 12884 KB Output is correct
25 Correct 39 ms 12884 KB Output is correct
26 Correct 42 ms 14804 KB Output is correct
27 Correct 49 ms 15060 KB Output is correct
28 Correct 46 ms 15060 KB Output is correct
29 Correct 49 ms 15156 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 3 ms 10744 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 3 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 3 ms 10588 KB Output is correct
14 Correct 14 ms 11308 KB Output is correct
15 Correct 27 ms 12112 KB Output is correct
16 Correct 40 ms 12480 KB Output is correct
17 Correct 54 ms 13368 KB Output is correct
18 Correct 67 ms 13268 KB Output is correct
19 Correct 54 ms 13272 KB Output is correct
20 Correct 53 ms 13360 KB Output is correct
21 Correct 52 ms 13392 KB Output is correct
22 Correct 44 ms 12756 KB Output is correct
23 Correct 40 ms 13012 KB Output is correct
24 Correct 40 ms 12884 KB Output is correct
25 Correct 39 ms 12884 KB Output is correct
26 Correct 42 ms 14804 KB Output is correct
27 Correct 49 ms 15060 KB Output is correct
28 Correct 46 ms 15060 KB Output is correct
29 Correct 49 ms 15156 KB Output is correct
30 Correct 146 ms 16840 KB Output is correct
31 Correct 177 ms 18064 KB Output is correct
32 Correct 232 ms 19404 KB Output is correct
33 Correct 311 ms 22744 KB Output is correct
34 Correct 133 ms 16564 KB Output is correct
35 Correct 327 ms 22780 KB Output is correct
36 Correct 313 ms 22604 KB Output is correct
37 Correct 334 ms 22528 KB Output is correct
38 Correct 315 ms 22848 KB Output is correct
39 Correct 316 ms 22536 KB Output is correct
40 Correct 288 ms 22256 KB Output is correct
41 Correct 307 ms 23752 KB Output is correct
42 Correct 301 ms 22640 KB Output is correct
43 Correct 220 ms 21880 KB Output is correct
44 Correct 208 ms 21840 KB Output is correct
45 Correct 232 ms 21760 KB Output is correct
46 Correct 220 ms 20740 KB Output is correct
47 Correct 225 ms 20428 KB Output is correct
48 Correct 266 ms 22736 KB Output is correct
49 Correct 274 ms 22812 KB Output is correct