제출 #1220479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220479		Rifal	운세 보기 2 (JOI14_fortune_telling2)	C++20	0 / 100	1 ms	320 KiB

fortune_telling2

#include <bits/stdc++.h>
#include <fstream>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define pb push_back
#define INF 20000000000
#define fi first
#define se second
//#define cin fin
//#define cout fout
using namespace std;
//double const EPS = 1e-14;
typedef long long ll;
//const ll P = 10007;
const ll mod = 1e9 + 7;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int Max = 2e5 + 5;
ll a[Max], b[Max], pos[Max];
vector<pair<ll,int>> mn, mx;
priority_queue<pair<ll,int>> pq, pq1;
ll seg[Max];
void Update(int x, int l, int r, int pos) {
    if(l == r) {
        seg[x] = 1;
    }
    else {
        int mid = (l+r)/2;
        if(pos <= mid) Update(x*2,l,mid,pos);
        else Update(x*2+1,mid+1,r,pos);
        seg[x] = seg[x*2]+seg[x*2+1];
    }
}
int sum(int x, int l, int r, int L, int R) {
    if(L <= l && r <= R) {
        return seg[x];
    }
    else if(l > R || r < L) {
        return 0;
    }
    else {
        int mid = (l+r)/2;
        return sum(x*2,l,mid,L,R)+sum(x*2+1,mid+1,r,L,R);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        mn.push_back({min(a[i],b[i]),i});
        mx.push_back({-max(b[i],a[i]),i});
    }
    sort(mn.begin(),mn.end());
    sort(mx.begin(),mx.end());
    for(int i = 0; i < m; i++) {
        int x; cin >> x;
        pq.push({-x,i});
        pq1.push({x,i});
    }
    ll ans = 0;
    for(int i = 0; i < mn.size(); i++) {
        while(!pq.empty() && -pq.top().fi < mn[i].fi) pq.pop();
        if(!pq.empty() && -pq.top().fi < max(a[mn[i].se],b[mn[i].se])) pos[mn[i].se] = pq.top().se;
        else if(!pq.empty()) pos[mn[i].se] = -1;
    }
    for(int i = 0; i < mx.size(); i++) {
      //  cout << -mx[i].fi << 'p' << endl;
        while(!pq1.empty() && -mx[i].fi <= pq1.top().fi) {
           // cout << pq1.top().fi << 'h' << endl;
           // cout << pq1.top().se << 'f' << endl;
            Update(1,0,m,pq1.top().se);
            pq1.pop();
        }
        int cnt = sum(1,0,m,pos[mx[i].se]+1,m);
      //  cout << a[mx[i].se] << ' ' << b[mx[i].se] << ' ' << pos[mx[i].se] << ' ' <<  cnt << endl;
        if(pos[mx[i].se] == -1 && cnt%2 == 0) ans += a[mx[i].se];
        else if(pos[mx[i].se] == -1 && cnt%2 == 1) ans += b[mx[i].se];
        else if(cnt%2 == 0) ans += max(a[mx[i].se],b[mx[i].se]);
        else ans += min(a[mx[i].se],b[mx[i].se]);
    }
    cout << ans << endl;
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65