oj.uz

답안 #236688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236688 2020-06-02T20:52:45 Z Lyestria 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 3000 ms 19200 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn=2e5+10;
int a[mn],b[mn],si[mn];
vector<int>seg[mn*4];
#define mid ((l+r)>>1)
void upd(int x,int l,int r,int a,int b){
    seg[x].push_back(b);
    if(l==r);
    else if(a<=mid)upd(x*2,l,mid,a,b);
    else upd(x*2+1,mid+1,r,a,b);
}
int numg(vector<int>&v,int x){
    return v.size()-(lower_bound(v.begin(),v.end(),x)-v.begin());
}
int query1(int x,int l,int r,int a,int b){
    if(l==r){
        if(a<=seg[x][0]&&seg[x][0]<b)return l;
        else return l-1;
    }
    else{
        if(numg(seg[x*2],a)-numg(seg[x*2],b))return query1(x*2+1,mid+1,r,a,b);
        else return query1(x*2,l,mid,a,b);
    }
}
bool num(int x,int l,int r,int a,int b,int c){
    if(l==a&&r==b)return numg(seg[x],c)&1;
    if(b<=mid)return num(x*2,l,mid,a,b,c);
    else if(a>mid)return num(x*2+1,mid+1,r,a,b,c);
    else return num(x*2,l,mid,a,mid,c)^num(x*2+1,mid+1,r,mid+1,b,c);
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        if(a[i]>b[i]){
            swap(a[i],b[i]);
            si[i]=1;
        }
    }
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        upd(1,1,k,i,x);
    }
    for(int i=1;i<mn;i++)sort(seg[i].begin(),seg[i].end());
    ll ans=0;
    for(int i=0;i<n;i++){
        int t=query1(1,1,k,a[i],b[i]);
        if(t)si[i]=1;
        si[i]^=num(1,1,k,t+1,k,a[i]);
        if(si[i])ans+=b[i];
        else ans+=a[i];
    }
    printf("%lld",ans);
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3086 ms 19200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3086 ms 19200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3086 ms 19200 KB Time limit exceeded
2 Halted 0 ms 0 KB -