oj.uz

답안 #223575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223575 2020-04-15T13:52:16 Z jovan_b 운세 보기 2 (JOI14_fortune_telling2) C++17
0 / 100
 8 ms 5248 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

int a[200005];
int b[200005];
int sp[25][200005];
int g[200005];
int treba[200005];
int lg[200005];
int bit[300005];

pair <int, int> t[200005];

int k;

int nadji(int x){
    /// poslednji manji jednak x
    int l = 1, r = k, res = 0;
    while(l <= r){
        int mid = (l+r)/2;
        if(t[mid].first <= x){
            l = mid+1;
            res = mid;
        }
        else r = mid-1;
    }
    return res;
}

int getmax(int l, int r){
    int j = lg[r-l+1];
    return max(sp[j][l], sp[j][r-(1<<j)+1]);
}

int bitget(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

void bitadd(int x){
    while(x <= 300000){
        bit[x]++;
        x += x & -x;
    }
}

map <int, int> u;
vector <int> vec[200005];
int kolko[200005];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n >> k;
    for(int i=2; i<=k; i++){
        lg[i] = 1 + lg[i/2];
    }
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i];
    }
    for(int i=1; i<=k; i++){
        cin >> t[i].first;
        t[i].second = i;
        g[i] = t[i].first;
    }
    sort(t+1, t+1+k);
    for(int i=1; i<=k; i++){
        sp[0][i] = t[i].second;
    }
    for(int j=1; (1<<j)<=k; j++){
        for(int i=1; i+(1<<j)-1<=k; i++){
            sp[j][i] = max(sp[j-1][i], sp[j-1][i+(1<<(j-1))]);
        }
    }
    for(int i=1; i<=n; i++){
        int p = min(a[i], b[i]);
        int d = max(a[i], b[i]);
        int x = nadji(p-1);
        int y = nadji(d-1);
        if(x >= y) continue;
        treba[i] = getmax(x+1, y);
    }
    vector <int> comp;
    for(int i=1; i<=n; i++){
        vec[treba[i]+1].push_back(i);
    }
    for(int i=1; i<=n; i++){
        comp.push_back(a[i]);
        comp.push_back(b[i]);
    }
    for(int i=1; i<=k; i++){
        comp.push_back(g[i]);
    }
    sort(comp.begin(), comp.end());
    int cmpr = 0;
    for(auto c : comp){
        if(!u[c]) u[c] = ++cmpr;
    }
    for(int i=k; i>=1; i--){
        bitadd(u[g[i]]);
        for(auto c : vec[i]){
            kolko[c] = k-i+1 - bitget(u[min(a[c], b[c])]);
        }
    }
    ll res = 0;
    for(int i=1; i<=n; i++){
        //cout << i << " " << treba[i] << " " << kolko[i] << endl;
        kolko[i] %= 2;
        if(a[i] >= b[i] || treba[i] == 0){
            if(kolko[i]) res += b[i];
            else res += a[i];
        }
        else{
            if(kolko[i]) res += a[i];
            res += b[i];
        }
    }
    cout << res;
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 65.0

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