Submission #377777

#	Time	Username	Problem	Language	Result	Execution time	Memory
377777		ntabc05101	Zoltan (COCI16_zoltan)	C++14	98 / 140	230 ms	16792 KiB

zoltan

#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;
                }

                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 (stderr)

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: 98 / 140