oj.uz

답안 #317634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
317634 2020-10-30T05:22:18 Z Saacoota 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 9 ms 1528 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ii pair < int , int >
#define pb push_back
#define eb emplace_back

using namespace std;

int f[200010][20] , BIT[200010] , c[200010];
ii a[200010];

void upl(int x) {
    for ( ; x > 0 ; x -= (-x & x))
        BIT[x]++;
}

int dwl(int x) {
    int tmp = 0;
    for ( ; x <= 200000 ; x += (-x & x))
        tmp += BIT[x];
    return tmp;
}

int get(int l,int r) {
    int k = __lg(r - l + 1);
    return max(f[l][k] , f[r - (1 << k) + 1][k]);
}

int main() {
    freopen("JOI14.INP","r",stdin);
    freopen("JOI14.OUT","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n , k;
    cin >> n >> k;
    vector < int > vc;
    vector < ii > cat;
    for (int i = 1 ; i <= n ; ++i) cin >> a[i].fi >> a[i].se;
    for (int i = 1 ; i <= k ; ++i) {
        cin >> c[i];
        vc.pb(c[i]);
    }
    sort(vc.begin(),vc.end());
    for (int i = 1 ; i <= k ; ++i) {
        c[i] = lower_bound(vc.begin() , vc.end() , c[i]) - vc.begin() + 1;
        f[c[i]][0] = i;
    }
    int l = __lg(k);
    for (int j = 1 ; j <= l ; ++j)
    for (int i = 1 ; i + (1 << j) - 1 <= k ; ++i)
    f[i][j] = max(f[i][j - 1] , f[i + (1 << (j - 1))][j - 1]);
    for (int i = 1 ; i <= n ; ++i) {
        int l = lower_bound(vc.begin() , vc.end() , min(a[i].fi , a[i].se)) - vc.begin() + 1;
        int r = lower_bound(vc.begin() , vc.end() , max(a[i].fi , a[i].se)) - vc.begin();
        //cout << l << ' ' << r << '\n';
        cat.eb(get(l , r) , i);
    }
    sort(cat.begin(),cat.end());
    int cur = 1;
    long long ans = 0;
    for (auto v : cat) {
        while (cur <= v.fi) upl(c[cur]) , cur++;
        int ma = max(a[v.se].fi , a[v.se].se);
        int res = k - (lower_bound(vc.begin() , vc.end() , ma) - vc.begin());
        ma = lower_bound(vc.begin() , vc.end() , ma) - vc.begin() + 1;
        res -= dwl(ma);
        if (v.fi) ans += ((a[v.se].fi < a[v.se].se) ^ (res & 1) ? a[v.se].se : a[v.se].fi);
        else ans += (res & 1 ? a[v.se].se : a[v.se].fi);
    }
    cout << ans;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     freopen("JOI14.INP","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |     freopen("JOI14.OUT","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 65.0

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