제출 #234596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234596		nafis_shifat	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	568 ms	29264 KiB

fortune_telling2

#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;
    
    
    
    
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65