Submission #987189

#	Time	Username	Problem	Language	Result	Execution time	Memory
987189		MrDeboo	Fish (IOI08_fish)	C++17	0 / 100	912 ms	56024 KiB

fish

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mod 998244353
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>;
int N,L,R;
int n,k,m;
int seg[2000000];
int slv(int l=1,int r=N,int in=1){
    if(r<L||l>R)return 1;
    if(l>=L&&r<=R)return seg[in];
    int mid=(l+r)/2;
    return (slv(l,mid,in*2)*slv(mid+1,r,in*2+1))%m;
}
void dod(int in){
    in+=N;
    seg[in]++;
    in/=2;
    while(in){
        seg[in]=(seg[in*2]*seg[in*2+1])%m;
        in/=2;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k>>m;
    vector<pair<int,int>>v;
    vector<int>vct[k];
    vector<int>cnt(k);
    vector<int>cntt(k);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        vct[b-1].push_back(a);
        cntt[b-1]++;
        v.push_back({a,b-1});
    }
    for(int i=0;i<k;i++){
        int cn=0,pr=0;
        sort(vct[i].begin(),vct[i].end());
        for(auto &w:vct[i]){
            if(w>=pr*2){
                cn++;
                pr=w;
            }
        }
        cnt[i]=cn;
    }
    sort(v.begin(),v.end());
    N=exp2(ceil(log2(k)));
    for(int i=0;i<k;i++)seg[i+N]=1;
    for(int i=N-1;i;i--)seg[i]=(seg[i*2]*seg[i*2+1])%m;
    int ans=0,l=0;
    map<int,int>mp;
    for(int i=0;i<v.size();i++)mp[v[i].second]=i;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    for(int i=0;i<v.size();i++){
        while(pq.size()&&v[i].first>=pq.top().first*2){
            dod(pq.top().second);
            pq.pop();
        }
        if(mp[v[i].second]!=i)continue;
        for(auto &w:vct[v[i].second])pq.push({w,v[i].second});
        int g=1;
        if(v[i].second>0){
            L=1,R=v[i].second;
            g*=slv();
        }
        if(v[i].second!=k-1){
            R=k;
            L=v[i].second+2;
            g*=slv();
        }
        // cout<<g<<' ';
        // cout<<cnt[v[i].second]<<' ';
        ans+=g*cnt[v[i].second];
        ans%=m;
        // cout<<v[i].first<<' '<<v[i].second<<' '<<ans<<endl;
    }
    cout<<ans;
}
/*
0110
1100
*/

Compilation message (stderr)

fish.cpp: In function 'int main()':
fish.cpp:59: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]
   59 |     for(int i=0;i<v.size();i++)mp[v[i].second]=i;
      |                 ~^~~~~~~~~
fish.cpp:61: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]
   61 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
fish.cpp:57:15: warning: unused variable 'l' [-Wunused-variable]
   57 |     int ans=0,l=0;
      |               ^

• 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