oj.uz

Submission #234596

# Submission time Handle Problem Language Result Execution time Memory
234596 2020-05-24T18:11:12 Z nafis_shifat Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 568 ms 29264 KB 
#include<bits/stdc++.h>
using namespace std;
const int mxn=2e5+1;

const int mx=3*mxn;
int tree[4*mx]={};

void update(int node,int b,int e,int p,int v) {
    
    if(b>p || e<p)return;
    if(b==e) {
        tree[node]=v;
        return;
    }
    
    int mid=b+e>>1;
    
    int left=node<<1;
    int right=left|1;
    update(left,b,mid,p,v);
    update(right,mid+1,e,p,v);
    tree[node]=max(tree[left],tree[right]);
}


int query(int node,int b,int e,int l,int r) {
    if(l>r)return -1;
    if(b>r || e<l)return -1;
    if(b>=l && e<=r)return tree[node];
    
    int mid=b+e>>1;
    int left=node<<1;
    int right=left|1;
    
    return max(query(left,b,mid,l,r),query(right,mid+1,e,l,r));
}


struct BIT {
    int bit[mx]={};
    void update(int p,int v) {
        for(;p>0;p-=p&-p)bit[p]+=v;
    }
    int query(int p,int s=0) {
        for(;p<mx;p+=p&-p)s+=bit[p];
        return s;
    }
};



int main() {
    int n,k;
    scanf("%d%d",&n,&k);
    
    int a[n+1],b[n+1];
    int qs[k+1];
    vector<int> v;
    long long ans[n+1];
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&a[i],&b[i]);
        v.push_back(a[i]);
        v.push_back(b[i]);
        
        ans[i]=a[i];
    }
    
    for(int i=1;i<=k;i++) {
        scanf("%d",&qs[i]);
        v.push_back(qs[i]);
    }
    
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=k;i++) {
        qs[i]=lower_bound(v.begin(),v.end(),qs[i])-v.begin()+1;
        update(1,1,mx,qs[i],i);
    }
    
    vector<int> td[k+2];
    for(int i=1;i<=n;i++) {
        int x=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
        int y=lower_bound(v.begin(),v.end(),b[i])-v.begin()+1;
        
        int rs=query(1,1,mx,min(x,y),max(x,y)-1);
        if(rs<=0) {
            td[1].push_back(i);
            continue;
        }
        ans[i]=max(a[i],b[i]);
        td[rs+1].push_back(i);
        
    }
    
    
    BIT bt;
    
    for(int i=k;i>0;i--) {
        
        bt.update(qs[i],1);
        for(int j:td[i]) {
            int p=lower_bound(v.begin(),v.end(),min(a[j],b[j]))-v.begin()+1;
            int r=bt.query(p);
            if(r&1)ans[j]=ans[j]^a[j]^b[j];

        }
    }
    long long res=0;
    for(int i=1;i<=n;i++)res+=ans[i];
    cout<<res<<endl;
    
    
    
    
}

Compilation message

fortune_telling2.cpp: In function 'void update(int, int, int, int, int)':
fortune_telling2.cpp:16:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=b+e>>1;
             ~^~
fortune_telling2.cpp: In function 'int query(int, int, int, int, int)':
fortune_telling2.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=b+e>>1;
             ~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a[i],&b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&qs[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2816 KB Output is correct
2 Correct 7 ms 2816 KB Output is correct
3 Correct 7 ms 2944 KB Output is correct
4 Correct 8 ms 2816 KB Output is correct
5 Correct 8 ms 2944 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Correct 7 ms 2816 KB Output is correct
11 Correct 7 ms 2816 KB Output is correct
12 Correct 7 ms 2944 KB Output is correct
13 Correct 7 ms 2816 KB Output is correct
14 Correct 26 ms 4088 KB Output is correct
15 Correct 44 ms 5364 KB Output is correct
16 Correct 67 ms 6640 KB Output is correct
17 Correct 88 ms 7920 KB Output is correct
18 Correct 89 ms 8048 KB Output is correct
19 Correct 91 ms 7928 KB Output is correct
20 Correct 98 ms 8048 KB Output is correct
21 Correct 88 ms 8048 KB Output is correct
22 Correct 63 ms 7020 KB Output is correct
23 Correct 63 ms 6764 KB Output is correct
24 Correct 65 ms 6512 KB Output is correct
25 Correct 67 ms 7280 KB Output is correct
26 Correct 68 ms 7024 KB Output is correct
27 Correct 80 ms 7532 KB Output is correct
28 Correct 67 ms 7536 KB Output is correct
29 Correct 84 ms 7792 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2816 KB Output is correct
2 Correct 7 ms 2816 KB Output is correct
3 Correct 7 ms 2944 KB Output is correct
4 Correct 8 ms 2816 KB Output is correct
5 Correct 8 ms 2944 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Correct 7 ms 2816 KB Output is correct
11 Correct 7 ms 2816 KB Output is correct
12 Correct 7 ms 2944 KB Output is correct
13 Correct 7 ms 2816 KB Output is correct
14 Correct 26 ms 4088 KB Output is correct
15 Correct 44 ms 5364 KB Output is correct
16 Correct 67 ms 6640 KB Output is correct
17 Correct 88 ms 7920 KB Output is correct
18 Correct 89 ms 8048 KB Output is correct
19 Correct 91 ms 7928 KB Output is correct
20 Correct 98 ms 8048 KB Output is correct
21 Correct 88 ms 8048 KB Output is correct
22 Correct 63 ms 7020 KB Output is correct
23 Correct 63 ms 6764 KB Output is correct
24 Correct 65 ms 6512 KB Output is correct
25 Correct 67 ms 7280 KB Output is correct
26 Correct 68 ms 7024 KB Output is correct
27 Correct 80 ms 7532 KB Output is correct
28 Correct 67 ms 7536 KB Output is correct
29 Correct 84 ms 7792 KB Output is correct
30 Correct 172 ms 14444 KB Output is correct
31 Correct 239 ms 17496 KB Output is correct
32 Correct 327 ms 21348 KB Output is correct
33 Correct 507 ms 29148 KB Output is correct
34 Correct 167 ms 13800 KB Output is correct
35 Correct 519 ms 29024 KB Output is correct
36 Correct 532 ms 28764 KB Output is correct
37 Correct 568 ms 28764 KB Output is correct
38 Correct 514 ms 28892 KB Output is correct
39 Correct 509 ms 28868 KB Output is correct
40 Correct 450 ms 29264 KB Output is correct
41 Correct 537 ms 28764 KB Output is correct
42 Correct 522 ms 28764 KB Output is correct
43 Correct 319 ms 24668 KB Output is correct
44 Correct 326 ms 25180 KB Output is correct
45 Correct 329 ms 25948 KB Output is correct
46 Correct 328 ms 22932 KB Output is correct
47 Correct 323 ms 21216 KB Output is correct
48 Correct 383 ms 26332 KB Output is correct
49 Correct 346 ms 26456 KB Output is correct