Submission #367853

#	Time	Username	Problem	Language	Result	Execution time	Memory
367853		leinad2	Fish (IOI08_fish)	C++17	100 / 100	1737 ms	38912 KiB

fish

#include<bits/stdc++.h>
using namespace std;
int n, i, j, k, mod, a, b, seg[2000010], A[500010], ans, X;
vector<int>v[500010];
vector<pair<int, int> >V;
void init(int id, int s, int e)
{
    if(s==e)
    {
        seg[id]=1;
        return;
    }
    int m=s+e>>1;
    init(id*2, s, m);
    init(id*2+1, m+1, e);
    seg[id]=(seg[id*2]*seg[id*2+1])%mod;
}
void update(int id, int s, int e, int x, int v)
{
    if(e<x||x<s)return;
    if(s==e)
    {
        seg[id]=v%mod;
        return;
    }
    int m=s+e>>1;
    update(id*2, s, m, x, v);
    update(id*2+1, m+1, e, x, v);
    seg[id]=(seg[id*2]*seg[id*2+1])%mod;
}
int get(int id, int s, int e, int l, int r)
{
    if(r<s||e<l)return 1;
    if(l<=s&&e<=r)return seg[id];
    int m=s+e>>1;
    return (get(id*2, s, m, l, r)*get(id*2+1, m+1, e, l, r))%mod;
}
bool cmp(vector<int>a, vector<int>b)
{
    return a.back()<b.back();
}
main()
{
    ios_base::sync_with_stdio(!cin.tie(NULL));
    for(cin>>n>>k>>mod;i++<n;)
    {
        cin>>a>>b;
        v[b].push_back(a);
    }
    n=k;
    for(i=0;i++<n;)sort(v[i].begin(), v[i].end());
    sort(v+1, v+n+1, cmp);
    for(i=0;i++<n;)
    {
        for(j=0;j<v[i].size();j++)
        {
            V.push_back({v[i][j], i});
        }
    }
    sort(V.begin(), V.end());
    init(1, 1, n);
    for(i=0;i++<n;)
    {
        while(X<V.size())
        {
            if(V[X].first*2<=v[i].back())
            {
                update(1, 1, n, V[X].second, ++A[V[X].second]+1);
                X++;
            }
            else break;
        }
        ans+=get(1, 1, n, 1, i);
        a=0;
        b=n;
        while(a<b)
        {
            int m=(a+b+1)>>1;
            if(v[m].back()<2*v[i][A[i]])a=m;
            else b=m-1;
        }
        ans+=(get(1, 1, n, 1, i-1)*(get(1, 1, n, i+1, b)-1));
        ans%=mod;
    }
    if(ans<0)ans+=mod;
    cout<<ans;
}

Compilation message (stderr)

fish.cpp: In function 'void init(int, int, int)':
fish.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int m=s+e>>1;
      |           ~^~
fish.cpp: In function 'void update(int, int, int, int, int)':
fish.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int m=s+e>>1;
      |           ~^~
fish.cpp: In function 'int get(int, int, int, int, int)':
fish.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m=s+e>>1;
      |           ~^~
fish.cpp: At global scope:
fish.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main()
      |      ^
fish.cpp: In function 'int main()':
fish.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
fish.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while(X<V.size())
      |               ~^~~~~~~~~

• 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