제출 #233718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233718		LittleFlowers__	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	496 ms	24028 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int N=200010;

int n,q;
int a[N],b[N],c[N];
vector<int> val;

int T[N*4];
int bit[N],pf[N],sf[N];
vector<ii> qry;

void upd(int s,int l,int r,int i,int x){
    if(l>i||i>r) return;
    if(l==r){
        T[s]=max(T[s],x);
        return;
    }
    int m=(l+r)/2;
    upd(2*s,l,m,i,x); upd(2*s+1,m+1,r,i,x);
    T[s]=max(T[2*s],T[2*s+1]);
}
int que(int s,int l,int r,int u,int v){
    if(l>v||u>r||u>v) return 0;
    if(u<=l&&r<=v) return T[s];
    int m=(l+r)/2;
    return max(que(2*s,l,m,u,v),que(2*s+1,m+1,r,u,v));
}

void upd(int i){
    i=lower_bound(all(val),i)-val.begin()+1;
    for(;i;i-=i&-i) bit[i]++;
}
int que(int i){
    i=lower_bound(all(val),i)-val.begin()+1;
    int ret=0;
    for(;i<=q;i+=i&-i) ret+=bit[i];
    return ret;
}

main(){
    #define task "fortune"
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);

    n=in,q=in;
    forinc(i,1,n) a[i]=in, b[i]=in;
    forinc(i,1,q) val.push_back(c[i]=in);
    sort(all(val)); ///, val.erase(unique(all(val)),val.end());

    forinc(i,1,q){
        int pos=lower_bound(all(val),c[i])-val.begin()+1;
        upd(1,1,q,pos,i);
    }

    forinc(i,1,n){
        int lf=lower_bound(all(val),min(a[i],b[i]))-val.begin()+1;
        int rt=lower_bound(all(val),max(a[i],b[i]))-val.begin();
        qry.push_back({pf[i]=que(1,1,q,lf,rt),i});
    }

    sort(all(qry));
    int j=1;
    forv(i,qry){
        while(j<=i.fi) upd(c[j++]);
        int dw=que(max(a[i.se],b[i.se]));
        int tot=lower_bound(all(val),max(a[i.se],b[i.se]))-val.begin(); tot=q-tot;
        sf[i.se]=tot-dw;
    }

    int tot=0;
    forinc(i,1,n){
        if(!pf[i]){
            tot+=sf[i]&1 ? b[i] : a[i];
        } else{
            tot+=(a[i]<b[i]) ^ (sf[i]&1) ? b[i] : a[i];
        }
    }
    cout<<tot;
}

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

fortune_telling2.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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