oj.uz

Submission #1094894

# Submission time Handle Problem Language Result Execution time Memory
1094894 2024-09-30T19:19:20 Z quicksloth Fish (IOI08_fish) C++17
80 / 100
 3000 ms 33104 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 3 ms 8656 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 120 ms 18248 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 12832 KB Output is correct
2 Correct 91 ms 14208 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8796 KB Output is correct
2 Correct 6 ms 8860 KB Output is correct
3 Correct 7 ms 8796 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 15432 KB Output is correct
2 Correct 194 ms 20096 KB Output is correct
3 Correct 172 ms 20048 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 20164 KB Output is correct
2 Correct 108 ms 19908 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 16208 KB Output is correct
2 Correct 147 ms 20300 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 19912 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 21516 KB Output is correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1847 ms 22844 KB Output is correct
2 Execution timed out 3065 ms 23724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 28540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3048 ms 20820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 33104 KB Time limit exceeded
2 Halted 0 ms 0 KB -