oj.uz

Submission #619971

# Submission time Handle Problem Language Result Execution time Memory
619971 2022-08-02T17:54:42 Z AbdelmagedNour Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 532 ms 31072 KB 
#include<bits/stdc++.h>
using namespace std;
struct SegTreeMax{
    int tree[1<<21];
    int sz;
    void init(int n){
        sz=1;
        while(sz<n)sz*=2;
        memset(tree,-1,2*sz*sizeof(tree[0]));
    }
    void update(int l,int r,int p,int idx,int val){
        if(l==r){
            tree[p]=val;
            return;
        }
        int md=(l+r)>>1;
        if(md>=idx)update(l,md,p*2+1,idx,val);
        else update(md+1,r,p*2+2,idx,val);
        tree[p]=max(tree[p*2+1],tree[p*2+2]);
    }
    void update(int idx,int val){
        update(0,sz-1,0,idx,val);
    }
    int query(int l,int r,int p,int l_q,int r_q){
        if(l>r_q||r<l_q)return -1;
        if(l>=l_q&&r<=r_q)return tree[p];
        int md=(l+r)>>1;
        int ch1=query(l,md,p*2+1,l_q,r_q);
        int ch2=query(md+1,r,p*2+2,l_q,r_q);
        return max(ch1,ch2);
    }
    int query(int l,int r){
        return query(0,sz-1,0,l,r);
    }
}treeMax;
struct SegTreeSum{
    int tree[1<<21];
    int sz;
    void init(int n){
        sz=1;
        while(sz<n)sz*=2;
        memset(tree,0,2*sz*sizeof(tree[0]));
    }
    void update(int l,int r,int p,int idx,int val){
        if(l==r){
            tree[p]+=val;
            return;
        }
        int md=(l+r)>>1;
        if(md>=idx)update(l,md,p*2+1,idx,val);
        else update(md+1,r,p*2+2,idx,val);
        tree[p]=(tree[p*2+1]+tree[p*2+2]);
    }
    void update(int idx,int val){
        update(0,sz-1,0,idx,val);
    }
    int query(int l,int r,int p,int l_q,int r_q){
        if(l>r_q||r<l_q)return 0;
        if(l>=l_q&&r<=r_q)return tree[p];
        int md=(l+r)>>1;
        int ch1=query(l,md,p*2+1,l_q,r_q);
        int ch2=query(md+1,r,p*2+2,l_q,r_q);
        return (ch1+ch2);
    }
    int query(int l,int r){
        return query(0,sz-1,0,l,r);
    }
}treeSum;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    int a[n][2],b[n][2],q[k][2],c[n];
    vector<int>V;
    for(int i=0;i<n;i++)cin>>a[i][0]>>b[i][0],V.push_back(a[i][0]),V.push_back(b[i][0]);
    for(int i=0;i<k;i++)cin>>q[i][0],V.push_back(q[i][0]);
    int id=0;
    sort(V.begin(),V.end());
    V.resize(unique(V.begin(),V.end())-V.begin());
    id=V.size();
    for(int i=0;i<n;i++){
        a[i][1]=lower_bound(V.begin(),V.end(),a[i][0])-V.begin();
        b[i][1]=lower_bound(V.begin(),V.end(),b[i][0])-V.begin();
    }
    for(int i=0;i<k;i++)q[i][1]=lower_bound(V.begin(),V.end(),q[i][0])-V.begin();
    vector<vector<int>>v(k+1);
    treeMax.init(id);
    treeSum.init(id);
    for(int i=0;i<k;i++)treeMax.update(q[i][1],i);
    for(int i=0;i<n;i++){
        int l=a[i][1],r=b[i][1];
        if(l>r)swap(l,r);
        int mx=-1;
        if(l<r)mx=treeMax.query(l,r-1);
        c[i]=mx;
        v[mx+1].push_back(i);
    }
    long long sum=0;
    for(int i=k;i>=0;i--){
        if(i<k)treeSum.update(q[i][1],1);
        for(auto&x:v[i]){
            int cnt=treeSum.query(max(a[x][1],b[x][1]),id);
            if(c[x]==-1){
                if(cnt&1)sum+=b[x][0];
                else sum+=a[x][0];
            }else{
                if(cnt&1)sum+=min(a[x][0],b[x][0]);
                else sum+=max(a[x][0],b[x][0]);
            }
        }
    }
    cout<<sum;
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 408 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 15 ms 1492 KB Output is correct
15 Correct 31 ms 2772 KB Output is correct
16 Correct 48 ms 4324 KB Output is correct
17 Correct 64 ms 5132 KB Output is correct
18 Correct 67 ms 5256 KB Output is correct
19 Correct 67 ms 5056 KB Output is correct
20 Correct 67 ms 5072 KB Output is correct
21 Correct 63 ms 5216 KB Output is correct
22 Correct 47 ms 5100 KB Output is correct
23 Correct 46 ms 4136 KB Output is correct
24 Correct 44 ms 4080 KB Output is correct
25 Correct 49 ms 5296 KB Output is correct
26 Correct 47 ms 4812 KB Output is correct
27 Correct 59 ms 5164 KB Output is correct
28 Correct 51 ms 5144 KB Output is correct
29 Correct 65 ms 5148 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 408 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 15 ms 1492 KB Output is correct
15 Correct 31 ms 2772 KB Output is correct
16 Correct 48 ms 4324 KB Output is correct
17 Correct 64 ms 5132 KB Output is correct
18 Correct 67 ms 5256 KB Output is correct
19 Correct 67 ms 5056 KB Output is correct
20 Correct 67 ms 5072 KB Output is correct
21 Correct 63 ms 5216 KB Output is correct
22 Correct 47 ms 5100 KB Output is correct
23 Correct 46 ms 4136 KB Output is correct
24 Correct 44 ms 4080 KB Output is correct
25 Correct 49 ms 5296 KB Output is correct
26 Correct 47 ms 4812 KB Output is correct
27 Correct 59 ms 5164 KB Output is correct
28 Correct 51 ms 5144 KB Output is correct
29 Correct 65 ms 5148 KB Output is correct
30 Correct 131 ms 11880 KB Output is correct
31 Correct 179 ms 17224 KB Output is correct
32 Correct 248 ms 18848 KB Output is correct
33 Correct 474 ms 30536 KB Output is correct
34 Correct 128 ms 11616 KB Output is correct
35 Correct 421 ms 30428 KB Output is correct
36 Correct 404 ms 30392 KB Output is correct
37 Correct 532 ms 30364 KB Output is correct
38 Correct 426 ms 30348 KB Output is correct
39 Correct 446 ms 30400 KB Output is correct
40 Correct 455 ms 31068 KB Output is correct
41 Correct 445 ms 30340 KB Output is correct
42 Correct 487 ms 30156 KB Output is correct
43 Correct 283 ms 31072 KB Output is correct
44 Correct 281 ms 30960 KB Output is correct
45 Correct 319 ms 30944 KB Output is correct
46 Correct 263 ms 22344 KB Output is correct
47 Correct 268 ms 18020 KB Output is correct
48 Correct 303 ms 22080 KB Output is correct
49 Correct 313 ms 22384 KB Output is correct