Submission #52764

#	Time	Username	Problem	Language	Result	Execution time	Memory
52764		Smelskiy	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	3039 ms	1828 KiB

fortune_telling2

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




int n,m;
int q[2000005];
int t1[2000005];
int t2[2000005];
int t3[2000005];
int t4[2000005];
pair<int,int> a[200005];
int sz;


inline void push(int x) {
    if (!q[x]) return;
    q[x+x]^=1;
    q[x+x+1]^=1;
    q[x]=0;
    swap(t1[x+x],t2[x+x]);
    swap(t1[x+x+1],t2[x+x+1]);
    swap(t3[x+x],t4[x+x]);
    swap(t3[x+x+1],t4[x+x+1]);
}

void dfs(int l,int r,int x,int y) {
    if (t3[x]>y) return;
    if (t1[x]<=y) {
        swap(t1[x],t2[x]);
        swap(t3[x],t4[x]);
        q[x]^=1;
        return;
    }
    if (l==r) return;
    int mid=(l+r)>>1;
    push(x);
    dfs(l,mid,x+x,y);
    dfs(mid+1,r,x+x+1,y);
    t1[x]=max(t1[x+x],t1[x+x+1]);
    t2[x]=max(t2[x+x],t2[x+x+1]);
    t3[x]=min(t3[x+x],t3[x+x+1]);
    t4[x]=min(t4[x+x],t4[x+x+1]);
}

long long ans=0;
void solve(int l,int r,int x) {
    if (l>n) return;
    if (l==r) {
        ans+=t1[x];
        return;
    }
    push(x);
    int mid=(l+r)>>1;
    solve(l,mid,x+x);
    solve(mid+1,r,x+x+1);
}

inline bool cmp(pair<int,int> x,pair<int,int> y) {
    return max(x.first,x.second)<max(y.first,y.second);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;++i) {
        cin>>a[i].first>>a[i].second;
    }
    random_shuffle(a+1,a+n+1);
    sz=1;
    while (sz<n) sz+=sz;
    for (int i=1;i<=n;++i) {
        t1[sz+i-1]=a[i].first;
        t2[sz+i-1]=a[i].second;
        t3[sz+i-1]=a[i].first;
        t4[sz+i-1]=a[i].second;
    }
    for (int i=sz-1;i>0;--i) {
        t1[i]=max(t1[i+i],t1[i+i+1]);
        t2[i]=max(t2[i+i],t2[i+i+1]);
        t3[i]=min(t3[i+i],t3[i+i+1]);
        t4[i]=min(t4[i+i],t4[i+i+1]);
    }
    int x;
    for (int i=1;i<=m;++i) {
        cin>>x;
        dfs(1,sz,1,x);
    }
    solve(1,sz,1);
    cout<<ans;
}

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