Submission #1094894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094894		quicksloth	Fish (IOI08_fish)	C++17	80 / 100	3065 ms	33104 KiB

fish

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
template<class C> using vc=vector<C>;
typedef int32_t i32;
#define For(i,a,b) for(i32 i=(a);i<(b);i++)
#define pb push_back
const i32 inf=0x7fffffff;
i32 mod;
struct prodtree
{
    static const i32 sz=19;
    i32 a[1<<(sz+1)];
    prodtree()
    {
        For(i,0,1<<(sz+1)) a[i]=1;
    }
    void set(i32 x, i32 v)
    {
        x+=1<<sz, a[x]=v%mod;
        while(x>>=1) a[x]=(a[2*x]*a[2*x+1])%mod;
    }
    i32 qry(i32 l, i32 r)
    {
        i32 ans=1;
        l+=1<<sz, r+=1<<sz;
        while(l!=r)
        {
            if(l&1) ans=(ans*a[l++])%mod;
            if(r&1) ans=(ans*a[--r])%mod;
            l>>=1, r>>=1;
        }
        return ans;
    }
};
/*
sizes for color i = v[i] (pad v[0] = 0); max = m[i], wlog m[i+1] >= m[i]
let b[i] = max value s.t. v[i][b[i]-1] <= m[i]/2
consider frequency array f[i]; when is m[k] ok but not m[>k]?
    f[k] in [1,b[k]]
    for any i!=k: v[i][f[i]] <= m[k]/2
    for any i>k, m[i] >= 2*v[k][f[k]]: f[i] not in [1,b[i]]
        if f[k] <= b[k]-1 then condition is just i>k
        if f[k] = b[k] then i>k is redundant
for k in increasing order:
    f[k] in [1,b[k]-1]:
        i!=k: v[i][f[i]] <= m[k]/2
        i>k: delete [1,b[i]]
    f[k] = b[k]:
        i!=k: v[i][f[i]] <= m[k]/2
        m[i] >= 2*v[k][b[k]]: delete [1,b[i]]
maintain 2 product trees
*/
int main()
{
    cin.sync_with_stdio(0),cin.tie(0);
    i32 n,k; vc<vc<i32>> v;
    {
        cin>>n>>k>>mod, v.resize(k);
        if(mod==1) cout<<1<<'\n', exit(0);
        i32 w,c; For(i,0,n) cin>>w>>c, v[c-1].pb(w);
        For(i,0,k) v[i].pb(0), sort(v[i].begin(),v[i].end());
        sort(v.begin(),v.end(),
            [&](vc<i32> v1, vc<i32> v2){return v1.back()<v2.back();});
    }
    vc<i32> m(k), b(k); vc<vc<i32>> upd(k); map<i32,i32> mp;
    {
        For(i,0,k) m[i]=v[i].back();
        For(i,0,k) if(mp.find(m[i])==mp.end()) mp[m[i]]=i; mp[inf]=k;
        For(i,0,k) For(j,0,v[i].size()) if(v[i][j]<=m[i]/2) b[i]=j+1;
        For(i,0,k)
        {
            i32 t=0; For(j,1,v[i].size())
            {
                while(v[i][j]>m[t]/2 && t<k) t++;
                if(t==k) break; upd[t].pb(i);
            }
        }
    }
    prodtree *rt1=new prodtree(), *rt2=new prodtree(); vc<i32> f(k,1);
    i32 ans=0; For(i,0,k) //i = k from equations
    {
        for(i32 t:upd[i])
        {
            if(f[t]>b[t]) rt2->set(t,f[t]-b[t]+1);
            rt1->set(t,++f[t]);
        }
        i32 pre=rt1->qry(0,i), suf=rt2->qry(i+1,k);
        i32 cut=mp.lower_bound(2*v[i][b[i]])->second;
        i32 cpre=rt1->qry(i+1,cut), csuf=rt2->qry(cut,k);
        ans=(ans+((b[i]-1)%mod)*(pre*suf%mod)+pre*(cpre*csuf%mod))%mod;
    }
    cout<<ans<<'\n';
}

Compilation message (stderr)

fish.cpp: In function 'int main()':
fish.cpp:9:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define For(i,a,b) for(i32 i=(a);i<(b);i++)
      |                    ^~~
fish.cpp:72:9: note: in expansion of macro 'For'
   72 |         For(i,0,k) if(mp.find(m[i])==mp.end()) mp[m[i]]=i; mp[inf]=k;
      |         ^~~
fish.cpp:72:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   72 |         For(i,0,k) if(mp.find(m[i])==mp.end()) mp[m[i]]=i; mp[inf]=k;
      |                                                            ^~
fish.cpp:9:35: warning: comparison of integer expressions of different signedness: 'i32' {aka 'int'} and 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define For(i,a,b) for(i32 i=(a);i<(b);i++)
      |                                   ^
fish.cpp:73:20: note: in expansion of macro 'For'
   73 |         For(i,0,k) For(j,0,v[i].size()) if(v[i][j]<=m[i]/2) b[i]=j+1;
      |                    ^~~
fish.cpp:9:35: warning: comparison of integer expressions of different signedness: 'i32' {aka 'int'} and 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define For(i,a,b) for(i32 i=(a);i<(b);i++)
      |                                   ^
fish.cpp:76:22: note: in expansion of macro 'For'
   76 |             i32 t=0; For(j,1,v[i].size())
      |                      ^~~
fish.cpp:79:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   79 |                 if(t==k) break; upd[t].pb(i);
      |                 ^~
fish.cpp:79:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   79 |                 if(t==k) break; upd[t].pb(i);
      |                                 ^~~

• 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: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5