oj.uz

Submission #377777

# Submission time Handle Problem Language Result Execution time Memory
377777 2021-03-15T04:21:55 Z ntabc05101 Zoltan (COCI16_zoltan) C++14
98 / 140
 230 ms 16792 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;
                }

                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
98.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 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 Incorrect 1 ms 492 KB Output isn't correct
8 Incorrect 1 ms 492 KB Output isn't correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 92 ms 13452 KB Output is correct
12 Correct 78 ms 12028 KB Output is correct
13 Correct 81 ms 11432 KB Output is correct
14 Correct 107 ms 12428 KB Output is correct
15 Correct 159 ms 14752 KB Output is correct
16 Correct 230 ms 16792 KB Output is correct
17 Incorrect 90 ms 14604 KB Output isn't correct
18 Incorrect 91 ms 14732 KB Output isn't correct
19 Incorrect 92 ms 14604 KB Output isn't correct
20 Incorrect 93 ms 14660 KB Output isn't correct