oj.uz

답안 #52272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52272 2018-06-25T07:30:14 Z 노영훈(#1346) 운세 보기 2 (JOI14_fortune_telling2) C++11
0 / 100
 2 ms 380 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, m, k;
int Q[MX];
pii C[MX];
vector<int> X;

struct SEG1{
    int tree[2*MX*4], n; // max seg
    void init(int sz){
        n=sz;
        for(int i=1; i<4*sz; i++) tree[i]=0;
    }
    void upt(int v, int s, int e, int pos, int val){
        if(pos<s || e<pos) return;
        tree[v]=max(tree[v], val);
        if(s==e) return;
        upt(v*2, s, (s+e)/2, pos, val);
        upt(v*2+1, (s+e)/2+1, e, pos, val);
    }
    void upt(int pos, int val){
        upt(1,1,n,pos,val);
    }
    int mx(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 max(mx(v*2, s, (s+e)/2, l, r), mx(v*2+1, (s+e)/2+1, e, l, r));
    }
    int mx(int l, int r){
        return mx(1,1,n,l,r);
    }
} MT;

struct SEG2{
    int tree[MX], n; // sum BIT
    void init(int sz){
        n=sz;
        for(int i=1; i<=n; i++) tree[i]=0;
    }
    void upt(int pos){
        for(; 0<pos && pos<=n; pos+=pos&(-pos))
            tree[pos]++;
    }
    int sum(int pos){
        int ans=0;
        for(; pos>0; pos-=pos&(-pos))
            ans+=tree[pos];
        return ans;
    }
    int sum(int l, int r){
        return sum(r)-sum(l-1);
    }
} ST;

int find(int x){
    // 이하인 최대 인덱스. 0~m
    return upper_bound(X.begin(), X.end(), x)-X.begin();
}

ll solve(){
    int idx[MX]; ll ans=0;
    iota(idx, idx+k+1, 0);
    sort(idx+1, idx+k+1, [](int a, int b){
        return Q[a]<Q[b];
    });

    ST.init(k);
    MT.init(X.size());

    for(int i=1, bck=k, frt=1; i<=n; i++){
        int x,y; tie(x,y)=C[i];
        if(x==y){ ans+=x; continue; }
        if(x>y) swap(x,y);

        while(bck>0 && Q[idx[bck]]>=y) ST.upt(idx[bck]), bck--;
        while(frt<=k && Q[idx[frt]]<y) MT.upt(find(Q[idx[frt]]), idx[frt]), frt++;

        int pos=MT.mx(find(x), find(y-1));
        if(pos==0){
            ans+= (ST.sum(pos+1, k)%2==1 ? C[i].second : C[i].first);
        }
        else{
            ans+= (ST.sum(pos+1, k)%2==1 ? x : y);
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i=1, a, b; i<=n; i++){
        cin>>a>>b;
        C[i]={a,b};
        X.push_back(a);
        X.push_back(b);
    }
    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end())-X.begin());
    for(int i=1; i<=k; i++) cin>>Q[i];
    cout<<solve();
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 65.0

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