제출 #317578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
317578		BJoozz	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	981 ms	51732 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
using ll = long long ;
//#define int long long

using ii = pair < int , int > ;
const int MAX = 200004,M=600004,mod=1e9+7;
const int inf=0x3f3f3f3f;
int K;
vector < int > pr[MAX];
ii a[MAX];
void maxx(int &a,int b){
if(b>a) a=b;
}

int t[MAX];
int F[M];
int val[M];
void upd(int id,int val){
    for(;id<M;id+=id&-id) maxx(F[id],val);
}
int get(int id){
    int res=0;;
    for(;id>0;id-=id&-id) maxx(res,F[id]);
    return res;
}
bool ok[MAX];
ii b[MAX];
void UPD(int id){
    for(;id>0;id-=id&-id)F[id]++;
}
int GET(int id){
    int res=0;
    for(;id<M;id+=id&-id)res+=F[id];
    return res;
}
bool cmp(ii u,ii v){
    return min(u.X,u.Y)>min(v.X,v.Y);
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("fortune.inp", "r", stdin);//freopen("fortune.out", "w", stdout);
    int n,m;
    cin>>n>>m;
    ll ans=0;
    vector < int > vec;
    map < int , int > mp;
    for(int i=1;i<=n;i++){
        cin>>a[i].X>>a[i].Y;
        if(a[i].X==a[i].Y) {ans+=a[i].X;i--;n--;continue;}
        vec.pb(a[i].X);
        vec.pb(a[i].Y);
    }
    for(int i=1;i<=m;i++){
        cin>>t[i];
        vec.pb(t[i]);
    }
    sort(vec.begin(),vec.end());
    int pre=0,cnt=0;

    for(int u:vec)if(u!=pre){
        val[++cnt]=u;
        mp[u]=cnt;
        pre=u;
    }
    //cout<<n<<'\n';
    for(int i=1;i<=n;i++){
        a[i].X=mp[a[i].X];
        a[i].Y=mp[a[i].Y];
    }
    for(int i=1;i<=m;i++){
        t[i]=mp[t[i]];
        //cout<<t[i]<<'\n';
        b[i]=ii(t[i],i);
    }
    sort(b+1,b+1+m,greater < ii > () );
    sort(a+1,a+1+n,cmp );
    for(int i=1,x,po=1;i<=n;i++){
        bool tt=0;
        if(a[i].X>a[i].Y) {swap(a[i].X,a[i].Y);ok[i]=1;}
        while(b[po].X>=a[i].X) {
            upd(b[po].X,b[po].Y);po++;
        }
        x=get(a[i].Y-1);
        pr[x].pb(i);
        //cout<<a[i].X<<' '<<a[i].Y<<' '<<t[x]<<' '<<x<<'\n';
        //if(tt)swap(a[i].X,a[i].Y);
    }
    memset(F,0,sizeof F);
    for(int i=m,x;i>0;i--){
        for(int u:pr[i]){
            x=GET(a[u].Y);
            //cout<<val[a[u].X]<<' '<<val[a[u].Y]<<' '<<x<<'\n';
            if(x&1) ans+=val[a[u].X];
            else ans+=val[a[u].Y];
        }
        UPD(t[i]);
    }

    for(int u:pr[0]){
        int x=GET(a[u].Y)^ok[u]^1;
        //cout<<val[a[u].X]<<' '<<val[a[u].Y]<<' '<<x<<'\n';
        if(x&1) ans+=val[a[u].X];
        else ans+=val[a[u].Y];
    }
    cout<<ans;


}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:82:14: warning: unused variable 'tt' [-Wunused-variable]
   82 |         bool tt=0;
      |              ^~

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