oj.uz

답안 #757714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
757714 2023-06-13T15:38:10 Z amogususus 운세 보기 2 (JOI14_fortune_telling2) C++17
0 / 100
 3000 ms 108364 KB 
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx,avx2,bmi")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define fout(name) freopen(name".out", "w", stdout);
using namespace std;
const int maxN=6e5+69;
const int mod=1e9+7;
const int bs=448;
ll n,q,a[maxN],b[maxN],c[maxN],BIT[maxN],st[20][maxN],oa[maxN],ob[maxN];
ll lg2(ll x){return x?__builtin_clzll(1)-__builtin_clzll(x):-1;}
void update(ll x,ll v){for(;x<maxN;x+=x&-x)BIT[x]+=v;}
ll get(ll x){
    if(x<0)return 0;
    ll r=0;
    for(;x;x-=x&-x)r+=BIT[x];
    return r;
}
ll getmax(ll L,ll R){
    if(L>R)return -1;
    ll i = lg2(R - L + 1);
    return max(st[i][L], st[i][R - (1 << i) + 1]);
}
vector<pll> v;
vector<ll> d;
vector<ll> query[maxN];
ll ans[maxN];
void Enter(){
    cin>>n>>q;
    for(int i=0;i<n;i++)cin>>a[i]>>b[i],d.pb(a[i]),d.pb(b[i]),oa[i]=a[i],ob[i]=b[i];
    for(int i=0;i<q;i++)cin>>c[i],d.pb(c[i]);
    sort(all(d));
    d.resize(unique(all(d))-d.begin());
    for(int i=0;i<n;i++)a[i]=lower_bound(all(d),a[i])-d.begin();
    for(int i=0;i<n;i++)b[i]=lower_bound(all(d),b[i])-d.begin();
    for(int i=0;i<q;i++)c[i]=lower_bound(all(d),c[i])-d.begin();

    memset(st,-1,sizeof st);
    for(ll i=0;i<q;i++)st[0][c[i]]=max(st[0][c[i]],i);
    for(int i=1;i<20;i++)
        for(int j=0;j+(1<<i)<=n+1;j++)
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    for(int i=0;i<n;i++){
        ll l=min(a[i],b[i]),r=max(a[i],b[i])-1,w=getmax(l,r);
        if(w!=-1)ans[i]=a[i]<b[i];
        else w=0;
        //cout<<i<<" "<<w<<endl;
        query[w].pb(i);
    }
    ll res=0;
    for(int i=q-1;i>=0;i--){
        update(c[i],1);
        for(auto x:query[i]){
            ll r=max(a[x],b[x])-1;
            ans[x]^=(get(n*3)-get(r))%2;
            if(ans[x])res+=ob[x];
            else res+=oa[x];
        }
    }
    cout<<res;
}
//amogus
signed main(){
    //open("seq198");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    ll t=1;
    //cin>>t;
    while(t--)
    Enter();
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3072 ms 108364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3072 ms 108364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3072 ms 108364 KB Time limit exceeded
2 Halted 0 ms 0 KB -