제출 #1176421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176421		vnedu	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	243 ms	76740 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 2e5 + 25;
const int K = 2e5 + 25;

int n,k,a[N],b[N],t[N];
namespace sub1
{
    bool check()
    {
        return (n<=1000 && k<=1000);
    }
    void solve()
    {
        for (int tri=1; tri<=k; ++tri)
        {
            int cur=t[tri];
            for (int i=1; i<=n; ++i) if (a[i]<=cur) swap(a[i],b[i]);
        }
        ll sum=0;
        for (int i=1; i<=n; ++i) sum+=a[i];
        cout<<sum;
    }
}
namespace subfull
{
    const int M = 6e5 + 65;
    const int inf  = INT_MAX/10;

    vector<int> v;
    int m,lst[M],lg[M],rmq[M][20];

    int getRmq(int l, int r)
    {
        if (l>r) return 0;
        int k=lg[r-l+1];
        int cur=max(rmq[l][k],rmq[r-(1<<k)+1][k]);
//        cout<<l<<' '<<r<<' '<<k<<' '<<cur<<'\n';
        return max(cur,0);
    }

    bool bit[M];
    void add(int x)
    {
        x=m-x+1;
        while (x<=m)
        {
            bit[x]^=1;
            x+=x&-x;
        }
    }
    bool get(int x)
    {
        x=m-x+1;
        bool ans=0;
        while (x>=1)
        {
            ans^=bit[x];
            x-=x&-x;
        }
        return ans;
    }

    vector<ii> query[M];
    int oldA[N],oldB[N];
    bool exchange[N];
    void solve()
    {
        for (int i=1; i<=n; ++i) v.pb(a[i]),v.pb(b[i]);
        for (int i=1; i<=k; ++i) v.pb(t[i]);
        sort(all(v)); v.erase(unique(all(v)),v.end());
        for (int i=1; i<=n; ++i)
        {
            oldA[i]=a[i];
            oldB[i]=b[i];
            a[i]=lower_bound(all(v),a[i])-v.begin()+1;
            b[i]=lower_bound(all(v),b[i])-v.begin()+1;
        }
        for (int i=1; i<=k; ++i)
        {
            t[i]=lower_bound(all(v),t[i])-v.begin()+1;
        }
        m=(int)v.size();
        for (int i=1; i<M; ++i) lst[i]=-inf;
        for (int i=1; i<=k; ++i) lst[t[i]]=i;
        for (int i=1; i<=m; ++i) rmq[i][0]=lst[i];
//        cout<<lst[8]<<' '<<rmq[8][0]<<'\n';
        for (int j=1; j<20; ++j) for (int i=1; i+(1<<j)-1<=m; ++i)
        {
            rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
        }
//        cout<<rmq[8][0];
//        return;
        for (int i=2; i<=m; ++i) lg[i]=lg[i>>1]+1;
        for (int i=1; i<=n; ++i)
        {
            int l=min(a[i],b[i]),r=max(a[i],b[i]);
            int last=getRmq(l,r-1);
            if (last!=0)
            {
                exchange[i]=(r!=a[i]);
                a[i]=r;
                b[i]=l;
            }
//            cout<<i<<' '<<last<<'\n';
            query[last+1].pb({r,i});
        }
        for (int tri=k+1; tri>=1; --tri)
        {
            if (tri<=k) add(t[tri]);
            for (ii &cm : query[tri])
            {
                bool cur=get(cm.fi);
                if (cur==1)
                {
                    int id=cm.se;
                    exchange[id]^=1;
                }
            }
        }
        ll ans=0;
        for (int i=1; i<=n; ++i)
        {
            if (exchange[i]) swap(oldA[i],oldB[i]);
            ans+=oldA[i];
        }
//        for (int i=1; i<=n; ++i) cout<<a[i]<<' ';
//        cout<<'\n';
        cout<<ans;
    }
}
void solve()
{
    cin>>n>>k;
    for (int i=1; i<=n; ++i) cin>>a[i]>>b[i];
    for (int i=1; i<=k; ++i) cin>>t[i];
    if (sub1::check()) return void(sub1::solve());
    return void(subfull::solve());
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

//    #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
//    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

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