oj.uz

답안 #272124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
272124 2020-08-18T09:30:36 Z mayhoubsaleh Nekameleoni (COCI15_nekameleoni) C++14
140 / 140
 1338 ms 66860 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define left 2*i+1
#define righ 2*i+2
#define mid (l+r)/2
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


using namespace std;
const ll maxn=1e5+100;
const ll inf=1e9+10;
const ll mod=1e9+7;
const ll base=27;

ll n,k,m;
ll a[maxn];
ll ans[4*maxn],len[4*maxn];
vector<pair<ll,ll>>suf[4*maxn],pre[4*maxn];

bool check(ll bit){
    return (bit+1==(1ll<<k));
}

void build(ll i,ll l,ll r){
    if(l==r){
        len[i]=1;
        ans[i]=inf;
        pre[i].pb({0,0});
        pre[i].pb({1,1ll<<a[r]});
        suf[i].pb({0,0});
        suf[i].pb({1,1ll<<a[r]});
        return;
    }
    build(left,l,mid);
    build(righ,mid+1,r);
    len[i]=len[left]+len[righ];
    for(auto x:pre[left])pre[i].pb(x);
    ll cur=pre[left].back().second;
    for(auto x:pre[righ]){
        if((x.second|cur)==cur)continue;
        cur|=x.second;
        pre[i].pb({len[left]+x.first,cur});
    }

    for(auto x:suf[righ])suf[i].pb(x);
    cur=suf[righ].back().second;
    for(auto x:suf[left]){
        if((x.second|cur)==cur)continue;
        cur|=x.second;
        suf[i].pb({len[righ]+x.first,cur});
    }

    ll p=pre[righ].size()-1;
    ll s=0;
    ans[i]=inf;
    while(p>=0&&s<suf[left].size()){
        if(check(pre[righ][p].second|suf[left][s].second)){
            ans[i]=min(ans[i],pre[righ][p].first+suf[left][s].first);
            p--;
        }
        else{
            s++;
        }
    }
    ans[i]=min(ans[i],min(ans[left],ans[righ]));
}

void upd(ll i,ll l,ll r,ll id){
    if(r<id||l>id)return;
    if(l==r){
        pre[i].clear();
        suf[i].clear();
        ans[i]=inf;
        pre[i].pb({0,0});
        pre[i].pb({1,1ll<<a[r]});
        suf[i].pb({0,0});
        suf[i].pb({1,1ll<<a[r]});
        return;
    }
    upd(left,l,mid,id);
    upd(righ,mid+1,r,id);
    //len[i]=len[left]+len[righ];
    pre[i].clear();suf[i].clear();
    for(auto x:pre[left])pre[i].pb(x);
    ll cur=pre[left].back().second;
    for(auto x:pre[righ]){
        if((x.second|cur)==cur)continue;
        cur|=x.second;
        pre[i].pb({len[left]+x.first,cur});
    }

    for(auto x:suf[righ])suf[i].pb(x);
    cur=suf[righ].back().second;
    for(auto x:suf[left]){
        if((x.second|cur)==cur)continue;
        cur|=x.second;
        suf[i].pb({len[righ]+x.first,cur});
    }

    ll p=pre[righ].size()-1;
    ll s=0;
    ans[i]=inf;
    while(p>=0&&s<suf[left].size()){
        if(check(pre[righ][p].second|suf[left][s].second)){
            ans[i]=min(ans[i],pre[righ][p].first+suf[left][s].first);
            p--;
        }
        else{
            s++;
        }
    }
    ans[i]=min(ans[i],min(ans[left],ans[righ]));


}

void pnod(int i,int l,int r){
    cout<<"***********************"<<endl;
    cout<<"Node ID: "<<i<<endl;
    cout<<"Node Range: ["<<l<<','<<r<<']'<<endl;
    cout<<"Node len: "<<len[i]<<endl;
    cout<<"Node prefixes:"<<endl;
    for(auto x:pre[i])cout<<"pre len: "<<x.first<<" pre bitmask "<<x.second<<endl;
    cout<<"Node suffixes:"<<endl;
    for(auto x:suf[i])cout<<"suf len: "<<x.first<<" suf bitmask "<<x.second<<endl;
    cout<<"Answer for this node: "<<ans[i]<<endl;
}
void print(int i,int l,int r){
    if(l==r){
        pnod(i,l,r);
        return;
    }
    print(left,l,mid);
    print(righ,mid+1,r);
    pnod(i,l,r);
}
int main()
{
    IOS
    cin>>n>>k>>m;
    for(ll i=0;i<n;i++){
        cin>>a[i];
        a[i]--;
    }

    build(0,0,n-1);
    //print(0,0,n-1);
    while(m--){
        ll t;
        cin>>t;
        if(t==1){
            ll p,val;
            cin>>p>>val;
            p--;val--;
            a[p]=val;
            upd(0,0,n-1,p);
        }
        else{
            if(ans[0]==inf)cout<<-1<<endl;
            else cout<<ans[0]<<endl;
        }
    }

    return 0;
}

Compilation message

nekameleoni.cpp: In function 'void build(long long int, long long int, long long int)':
nekameleoni.cpp:57:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     while(p>=0&&s<suf[left].size()){
      |                 ~^~~~~~~~~~~~~~~~~
nekameleoni.cpp: In function 'void upd(long long int, long long int, long long int, long long int)':
nekameleoni.cpp:104:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     while(p>=0&&s<suf[left].size()){
      |                 ~^~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 20480 KB Output is correct
2 Correct 24 ms 20352 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 21248 KB Output is correct
2 Correct 35 ms 21140 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 21624 KB Output is correct
2 Correct 45 ms 21632 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 377 ms 29688 KB Output is correct
2 Correct 930 ms 55824 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 649 ms 44920 KB Output is correct
2 Correct 994 ms 63808 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 793 ms 40332 KB Output is correct
2 Correct 999 ms 59788 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 978 ms 51908 KB Output is correct
2 Correct 1018 ms 60936 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 986 ms 48352 KB Output is correct
2 Correct 1218 ms 62604 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1338 ms 66656 KB Output is correct
2 Correct 1208 ms 65700 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1167 ms 66860 KB Output is correct
2 Correct 1012 ms 65656 KB Output is correct