oj.uz

Submission #377778

# Submission time Handle Problem Language Result Execution time Memory
377778 2021-03-15T04:22:42 Z ntabc05101 Zoltan (COCI16_zoltan) C++14
140 / 140
 172 ms 14732 KB 
#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>

#define f first
#define s second

const int max_n=200000;
const int mod=1e9+7;

std::pair<int, int> bits[max_n+5], bits2[max_n+5];

void update(int x, std::pair<int, int> delta) {
        assert(x>0);
        for (; x<=max_n; x+=x&-x) {
                if (bits[x].f<delta.f) {
                        bits[x]=delta;
                }
                else if (bits[x].f==delta.f) {
                        bits[x].s+=delta.s;
                        if (bits[x].s>=mod) {
                                bits[x].s-=mod;
                        }
                }
        }
}

std::pair<int, int> get(int x) {
        std::pair<int, int> ret={0, 0};
        for (; x>0; x&=x-1) {
                if (ret.f<bits[x].f) {
                        ret=bits[x];
                }
                else if (ret.f==bits[x].f) {
                        ret.s+=bits[x].s;
                        if (ret.s>=mod) {
                                ret.s-=mod;
                        }
                }
        }

        return ret;
}

void update2(int x, std::pair<int, int> delta) {
        for (; x>0; x&=x-1) {
                if (bits2[x].f<delta.f) {
                        bits2[x]=delta;
                }
                else if (bits2[x].f==delta.f) {
                        bits2[x].s+=delta.s;
                        if (bits2[x].s>=mod) {
                                bits2[x].s-=mod;
                        }
                }
        }
}

std::pair<int, int> get2(int x) {
        assert(x>0);
        std::pair<int, int> ret={0, 0};
        for (; x<=max_n; x+=x&-x) {
                if (ret.f<bits2[x].f) {
                        ret=bits2[x];
                }
                else if (ret.f==bits2[x].f) {
                        ret.s+=bits2[x].s;
                        if (ret.s>=mod) {
                                ret.s-=mod;
                        }
                }
        }

        return ret;
}


int main() {
        if (fopen("input.txt", "r")) {
                freopen("input.txt", "r", stdin);
                freopen("output.tx", "w", stdout);
        }

        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int n; std::cin>>n;
        int a[n];
        std::vector<int> points;
        for (int i=0; i<n; ++i) {
                std::cin>>a[i];
                points.push_back(a[i]);
        }

        std::sort(begin(points), end(points));
        points.resize(std::distance(begin(points), std::unique(begin(points), end(points))));

        std::unordered_map<int, int> cpts;
        for (int i=0; i<points.size(); ++i) {
                cpts[points[i]]=i+1;
        }
        for (int i=0; i<n; ++i) {
                a[i]=cpts[a[i]];
        }

        int64_t pow2[n+5];
        pow2[0]=1;
        for (int i=1; i<=n; ++i) {
                pow2[i]=(pow2[i-1]*2)%mod;
        }

        //for (int i=0; i<n; ++i) std::cout<<a[i]<<" "; std::cout<<"\n";

        update(1, {0, 1}); //[0] + 1
        update2(n, {0, 1}); //[n+1] - 1

        std::pair<int, int> result={0, 0};
        for (int i=n-1; i>=0; --i) {
                auto inc=get(a[i]), dec=get2(a[i]);
                //std::cout<<inc.f<<" "<<dec.f<<"\n";

                int len=inc.f+dec.f+1;
                int count=pow2[n-len]*inc.s%mod*dec.s%mod;

                if (result.f<len) {
                        result={len, count};
                }
                else if (result.f==len) {
                        result.s+=count;
                        if (result.s>=mod) {
                                result.s-=mod;
                        }
                }

                update(a[i]+1, {inc.f+1, inc.s});
                update2(a[i]-1, {dec.f+1, dec.s});
        }

        std::cout<<result.f<<" "<<result.s<<"\n";

        return 0;
}

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:99:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int i=0; i<points.size(); ++i) {
      |                       ~^~~~~~~~~~~~~~
zoltan.cpp:81:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   81 |                 freopen("input.txt", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:82:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   82 |                 freopen("output.tx", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 85 ms 12300 KB Output is correct
12 Correct 75 ms 10892 KB Output is correct
13 Correct 71 ms 10408 KB Output is correct
14 Correct 106 ms 11012 KB Output is correct
15 Correct 143 ms 13068 KB Output is correct
16 Correct 172 ms 14732 KB Output is correct
17 Correct 94 ms 13472 KB Output is correct
18 Correct 91 ms 13324 KB Output is correct
19 Correct 92 ms 13324 KB Output is correct
20 Correct 88 ms 13324 KB Output is correct