제출 #1245534

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

fortune_telling2

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define MASK(i) ((1)<<(i))
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_asince_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=2e5+1;
int n,m,crr=0;
int a[nmax],b[nmax],c[nmax];
int mx[4*nmax],mn[4*nmax],tree[nmax],ans[nmax],save[nmax];
bool flag=false;
map<int,int> mp;
set<int> s;

void input()
{
    cin >> n >> m;
    FOR(i,1,n) cin >> a[i] >> b[i];
    FOR(i,1,m) cin >> c[i];
}

void build(int id,int l,int r)
{
    if(l==r)
    {
        mx[id]=c[l];
        mn[id]=c[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    mx[id]=max(mx[id*2],mx[id*2+1]);
    mn[id]=min(mn[id*2],mn[id*2+1]);
}

int get(int id,int l,int r,int a,int b)
{
    if(l==r) return l;
    if(mx[id]<a || b<=mn[id]) return 0;
    int mid=(l+r)/2;
    if(mn[id*2+1]<b && a<=mx[id*2+1])
    {
        flag=true;
        return get(id*2+1,mid+1,r,a,b);
    }
    else return get(id*2,l,mid,a,b);
}
void compress()
{
    FOR(i,1,m) s.insert(c[i]);
    FORD(i,s) mp[i]=++crr;
}

void update(int x)
{
    while(x>0)
    {
        tree[x]++;
        x-=(x&-x);
    }
}

int get(int x)
{
    int ans=0;
    while(x<=crr)
    {
        ans+=tree[x];
        x+=(x&-x);
    }
    return ans;
}

void bit()
{
    compress();
    REP(i,m,1)
    {
        ans[i]=get(mp[c[i]]);
        update(mp[c[i]]);
    }
}

int bs(int x)
{
    int l=0,r=n+1;
    while(l+1<r)
    {
        int mid=(l+r)/2;
        if(save[mid]>=x) r=mid;
        else l=mid;
    }
    return r;
}

void solve()
{
    build(1,1,m);
    bit();
    int res=0;
    FOR(i,1,n)
    {
        int x=min(a[i],b[i]);
        int y=max(a[i],b[i]);
        flag=false;
        int lst=get(1,1,m,x,y);
        
        if(flag)
        {
            if(ans[lst]%2==1) res+=x;
            else res+=y;
        }
        else
        {
            int rm=get(bs(a[i]));
            if(rm%2==0) res+=a[i];
            else res+=b[i];
        }
    }
    cout << res;
}

signed main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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