Submission #1277893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277893		longdeptrai	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	552 ms	53108 KiB

fortune_telling2

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define LongDepTrai "task"
#define ll long long
#define int long long
#define ull unsigned long long
#define ld long double
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) int((x).size())

const int N=7e5+9;
int n,k,a[N],ac[N],bc[N],b[N],t[N],mark[N],node[4*N],beo[4*N],chodo[N*4];
void Update(int i,int l,int r,int pos,int val){
    if(l>pos || r<pos) return;
    if(l==r){
        node[i]=val;
        return;
    }
    Update(i*2,l,(l+r)/2,pos,val);
    Update(i*2+1,(l+r)/2+1,r,pos,val);

    node[i]=max(node[i*2],node[i*2+1]);
}
int Find(int i,int l,int r,int u,int v){
    if(l>v || r<u) return -1;
    if(l<=u && v<=r) return node[i];
    return max(Find(i*2,l,r,u,(u+v)/2),Find(i*2+1,l,r,(u+v)/2+1,v));
}
void Update2(int i,int l,int r,int pos,int val){
    if(l>pos || r<pos) return;
    if(l==r){
        chodo[i]+=val;
        return;
    }
    Update2(i*2,l,(l+r)/2,pos,val);
    Update2(i*2+1,(l+r)/2+1,r,pos,val);

    chodo[i]=chodo[i*2]+chodo[i*2+1];
}
int Find3(int i,int l,int r,int u,int v){
    if(l>v || r<u) return 0;
    if(l<=u && v<=r) return chodo[i];
    return Find3(i*2,l,r,u,(u+v)/2)+Find3(i*2+1,l,r,(u+v)/2+1,v);
}
vi v;
int idx(int val){
    return((lower_bound(v.begin(),v.end(),val)-v.begin())+1);
}
    vii qr;

bool cmp(ii x,ii y){
    return(x.fi>y.fi||(x.fi==y.fi && max(a[x.se],b[x.se])>max(a[y.se],b[y.se])));
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    if(fopen(LongDepTrai".inp","r")){
        freopen(LongDepTrai".inp","r",stdin);
        freopen(LongDepTrai".out","w",stdout);
    }

    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        v.pb(a[i]);
        v.pb(b[i]);
    }

    for(int i=1;i<=k;i++){
        cin>>t[i];
        v.pb(t[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int m=v.size();
    for(int i=1;i<=k;i++){
        Update(1,1,m,idx(t[i]),i);
    }
    for(int i=1;i<=n;i++){
        ac[i]=idx(a[i]);
        bc[i]=idx(b[i]);
    }
    for(int i=1;i<=n;i++){
        int l = ac[i];
        int r = bc[i];
        if(l > r) swap(l, r);
        r--;
        int j = 0;
        if (l <= r) {
            j = Find(1, l, r, 1, m);
            if (j < 0) j = 0;
        } else {
            j = 0;
        }
        if (j && a[i] < b[i]) swap(a[i], b[i]), swap(ac[i], bc[i]);

        qr.pb({j,i});
    }
    int res=0;
    sort(qr.begin(),qr.end(),cmp);
    int j=k;
    for(ii x:qr){
        while (j >= max(x.fi,1ll)) {
            Update2(1,1,m,idx(t[j]),1);
            j--;
        }
        if(x.fi==0){
            int tmp=Find3(1,max(ac[x.se],bc[x.se]),m,1,m);
            if(tmp&1) swap(a[x.se],b[x.se]);
        }
        else
        {
            int tmp=Find3(1,ac[x.se],m,1,m);
            if(tmp&1) swap(a[x.se],b[x.se]);
        }
    }
    for(int i=1;i<=n;i++){
        res+=a[i];
    }
    cout<<res;
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(LongDepTrai".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(LongDepTrai".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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