제출 #1316919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316919		erering	Fish (IOI08_fish)	C++20	100 / 100	983 ms	51300 KiB

fish

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
const int N=5e5+5,MAXA=1e6+5,inf=1e9,MOD=1e9+7;
pair<int,int> fsh[N];
vector<int> pos[N];
/*
 * take stuff not seen
 * in that case have segtree0 which consists of how many ways and remove all occurences of type x after u finish calculating it
 * take stuff seen but cant eat u in that case update all type x in segtree1 to 1 and calculate how many ways (basically taking all type x)
 */
int seg[N*4],offset=1,m;
void update(int idx,int val){
    idx+=offset;
    seg[idx]+=val;
    idx/=2;
    while(idx>0){
        seg[idx]=seg[idx*2]*seg[idx*2+1]%m;
        idx/=2;
    }
}
int query(int node,int qlo,int qhi,int lo,int hi){
    if(lo>=qlo && hi<=qhi)return seg[node];
    if(lo>qhi || hi<qlo)return 1;
    int mid=(lo+hi)/2;
    return query(node*2,qlo,qhi,lo,mid)*query(node*2+1,qlo,qhi,mid+1,hi)%m;
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int f,k; cin>>f>>k>>m; //m=1e9;
    for(int i=0;i<N*4;i++)seg[i]=1;
    while(offset<=f)offset*=2;
    for(int i=1;i<=f;i++)cin>>fsh[i].first>>fsh[i].second;
    sort(fsh+1,fsh+f+1);
    for(int i=1;i<=f;i++)pos[fsh[i].second].pb(i);
    for(int i=1;i<=f;i++)update(pos[fsh[i].second].back(),1);
    int in=f,ans=0;
    for(int i=f;i>=1;i--){
        int length=fsh[i].first,color=fsh[i].second;
        if(pos[color].back()!=i)continue;
     //   cout<<in<<endl;
        if(in<i)update(i,1);
        while(in>0 && fsh[in].first*2>length){
            if(in!=i)update(pos[fsh[in].second].back(),-1);
            in--;
        }
        int cur=pos[color].size()-1;
        while(cur>0 && length<2*fsh[pos[color][cur]].first)cur--;
        if(length>=2*fsh[pos[color][cur]].first)cur++;
        int l=i,r=f;
        while(l<r){
            int mid=(l+r+1)/2;
            if(fsh[mid].first>=fsh[pos[color][cur]].first*2)r=mid-1;
            else l=mid;
        }
        int og=seg[i+offset];
        update(i,-2); //remove case of choosing maximum and nothing
        ans+=query(1,1,i,0,offset-1);
     //   cout<<ans<<' ';
        update(i,1-seg[i+offset]); //forcing to choose maximum
     //   cout<<seg[4+offset]<<'s'<<endl;
        ans+=query(1,1,r,0,offset-1);
        update(i,og-2);  //resetting it to old value but removing i
        ans%=m;
      //  cout<<ans<<endl;
    }
    cout<<ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5