oj.uz

답안 #52245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52245 2018-06-25T06:00:16 Z 노영훈(#1346) 운세 보기 2 (JOI14_fortune_telling2) C++11
0 / 100
 3 ms 1144 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=200010, inf=2e9;

int n, k;
int A[MX], B[MX], Q[MX];
pii C[MX];

int tree[MX*8];

void upt(int v, int s, int e, int x){
    if(x<s || e<x) return;
    if(s==e){
        tree[v]++;
        return;
    }
    upt(v*2,s,(s+e)/2,x);
    upt(v*2+1,(s+e)/2+1,e,x);
    tree[v]=tree[v*2]+tree[v*2+1];
}

int cnt(int v, int s, int e, int l, int r){
    if(e<l || r<s) return 0;
    if(l<=s && e<=r) return tree[v];
    return cnt(v*2,s,(s+e)/2,l,r) + cnt(v*2+1,(s+e)/2+1,e,l,r);
}

int cnt(int l, int r){
    return cnt(1,0,k,l,r);
}

ll solve(){
    ll ans=0;
    int mn[MX]={};
    mn[k]=Q[k];
    for(int i=k-1; i>0; i--){
        mn[i]=min(mn[i+1], Q[i]);
    }

    sort(C+1, C+n+1, [](pii &a, pii &b){
        return max(a.first, a.second)>max(b.first, b.second);
    });

    int idx[MX];
    iota(idx, idx+k+1, 0);
    sort(idx+1, idx+k+1, [](int a, int b){
        return Q[a]>Q[b];
    });

    for(int i=1, pos=1; i<=n; i++){
        int x, y; tie(x,y)=C[i];
        // cout<<"WORKING ON: "<<x<<' '<<y<<'\n';
        if(x>y) swap(x,y);
        while(pos<=k && Q[idx[pos]]>=y){
            upt(1,0,k,idx[pos]);
            pos++;
        }
        if(x==y){
            // cout<<"SAME!!\n";
            ans+=x;
            continue;
        }
        int l=upper_bound(mn+1, mn+k+1, y-1)-mn-1;
        // ll old=ans;
        // cout<<"l: "<<l<<", cnt(l~k): "<<cnt(l,k)<<'\n';
        if(l==0){
            // starts from C[i].first
            ans+= (cnt(l, k)%2==1 ? C[i].second : C[i].first);
        }
        else{
            // starts from y
            ans+= (cnt(l, k)%2==1 ? x : y);
        }
        // cout<<ans-old<<'\n';
    }
    return ans;
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++){
        cin>>A[i]>>B[i];
        C[i]={A[i], B[i]};
    }
    for(int i=1; i<=k; i++){
        cin>>Q[i];
    }
    cout<<solve();
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 65.0

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