oj.uz

답안 #234591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234591 2020-05-24T17:49:00 Z nafis_shifat 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 6 ms 1280 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[mxn]={};
    void update(int p,int v) {
        for(;p>0;p-=p&-p)bit[p]+=v;
    }
    int query(int p,int s=0) {
        for(;p<mxn;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)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(),max(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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Incorrect 6 ms 1280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Incorrect 6 ms 1280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Incorrect 6 ms 1280 KB Output isn't correct
3 Halted 0 ms 0 KB -