제출 #1316184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316184		erering	Fish (IOI08_fish)	C++20	0 / 100	384 ms	52576 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][2],offset=1,m;
void update(int idx,int val,int type){
    idx+=offset;
    seg[idx][type]=val%m;
    idx/=2;
    while(idx>0){
        seg[idx][type]=seg[idx*2][type]*seg[idx*2+1][type]%m;
        idx/=2;
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int f,k; cin>>f>>k>>m;
    for(int i=0;i<N*4;i++)seg[i][0]=seg[i][1]=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++){
        if(pos[fsh[i].second].back()==i){
            update(fsh[i].second,pos[fsh[i].second].size()+1,0);
            update(fsh[i].second,pos[fsh[i].second].size()+1,1);
        }
    }
    int in=f,ce=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;
        if(in==i){
            update(color,seg[color+offset][0]-1,0);
            update(color,seg[color+offset][1]-1,1);
            in--;
        }
        while(in>0 && fsh[in].first*2>length){
            if(seg[fsh[in].second+offset][0]>1)update(fsh[in].second,seg[fsh[in].second+offset][0]-1,0);
            if(seg[fsh[in].second+offset][1]>1)update(fsh[in].second,seg[fsh[in].second+offset][1]-1,1);
            in--;
        }
        int og=seg[color+offset][0];
        update(color,og-1,0); //to prevent us picking maximum since we take care of that in seg1
        ans=(ans+seg[1][0])%m;
        update(color,1,0);
        int last=pos[color].size()-1;
        while(last>0 && length<2*pos[color][last])last--;
        if(length>=2*pos[color][last])last++;
        while(ce>i && fsh[ce].first>=pos[color][last]*2){
            update(fsh[ce].second,1,1);
            ce--;
        }
        og=seg[color+offset][1];
        update(color,1,1);
        ans=(ans+seg[1][1])%m;
        update(color,og,1);
     //   cout<<ans<<endl;
    }
    cout<<ans;
}

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