oj.uz

Submission #1025626

# Submission time Handle Problem Language Result Execution time Memory
1025626 2024-07-17T08:18:11 Z _rain_ Zoltan (COCI16_zoltan) C++14
21 / 140
 80 ms 5848 KB 
#include<bits/stdc++.h>
using namespace std;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
namespace Random
{
    #define int long long
    int Rand(int l , int r)
    {
        return uniform_int_distribution<int>(l , r)(rng);
    }
    #undef int 
}

using i64 = long long;
using ui64 = unsigned long long;

#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define sz(x) (x).size()
#define all(x) (x).begin() , (x).end()

#define FOR(i ,a , b) for (int i = (a); i <= (b); ++i)
#define FORD(i , a , b) for (int i = (b); i >= (a); --i)
#define REP(i , a , b) for (int i = (a); i < (b); ++i)
#define REPD(i , a , b) for (int i = (b) - 1 ; i >= (a); --i)

template <class T> 
    void compress(vector<T> &a)
    {
        sort(a.begin() , a.end());
        a.resize(unique(a.begin() , a.end()) - a.begin());
        return;
    }
template<class T>
    void printArr(T& container , string separator = "" , string finish = "\n")
    {
        for (auto& item : container) cout << item << separator;
        cout << finish;
    }

template<class T>
    bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
    bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
    T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
    T lcm(T x , T y) {return (x * y) / gcd(x , y);}

//... INPUT
    void INPUT(string name)
    {
        iostream::sync_with_stdio(false); cin.tie(0);
        if (!fopen((name + ".inp").c_str() , "r")) return;
        freopen((name + ".inp").c_str() , "r" , stdin);
        freopen((name + ".out").c_str() , "w+" , stdout);
    }

const int maxn = 2e5;
//... MOD OPERATOR
    const int MOD = 1e9 + 7;
    int add(int a , int b)
    {
        return (a + b >= MOD ? a + b - MOD : a + b);
    }
    int mul(int a , int b)
    {
        return (i64)a * b % MOD;
    }
    int binpow(int a , int b)
    {
        int res = 1;
        for (; b; b >>= 1 , a = mul(a,a))
            if (b&1) res = mul(res , a);
        return res;
    }
//... FEN
    class fenwick
    {
        public:
            vector<int> BIT;
            int n;

            void init(int _n)
            {
                n = _n;
                BIT.assign(n + 2 , {0});
                return;
            }
            void upd(int pos , int val)
                {
                    for (; pos <= n ; pos += pos & -pos)
                        BIT[pos] += val;
                    return;
                }
            int get(int pos)
            {
                int sum = 0;
                for (; pos; pos -= pos&-pos)
                    sum += BIT[pos];
                return sum;
            }
            int sum_range(int l , int r)
                {
                    return get(r) - get(l - 1);
                }
    };

fenwick LIS , LDS;
int n , a[maxn + 2];

int32_t main()
{
    INPUT("main");
        cin >> n;
        vector<int> value;
        FOR(i,1,n) 
            {
                cin >> a[i];
                value.push_back(a[i]);
            }
        compress(value);
        int length = sz(value); LIS.init(length); LDS.init(length);
        FOR(i,1,n) a[i] = upper_bound(all(value),a[i]) - value.begin();
        int mxlength = 0 , cnt = 0;
        FORD(i,1,n)
        {
            int dec = LDS.sum_range(a[i] + 1 , length);
            int inc = LIS.sum_range(1 , a[i] - 1);
            int x1 = LDS.sum_range(a[i],a[i]) , x2 = LIS.sum_range(a[i],a[i]);

            if (maximize(mxlength , dec + inc + 1)) cnt = 1;
                else if (mxlength == dec + inc + 1) ++cnt;
            LIS.upd(a[i],-x1); LDS.upd(a[i] , -x2);
            LIS.upd(a[i],1); LDS.upd(a[i],1);
        }
        cout << mxlength << ' ' << mul(cnt , binpow(2 , n - mxlength));
    cerr << "\nTIME RUN : " << 1000 * clock()/CLOCKS_PER_SEC << " MS \n";

}
/** lockheed martin build me - Red Bull boost me **/

Compilation message

zoltan.cpp: In function 'void INPUT(std::string)':
zoltan.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen((name + ".inp").c_str() , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen((name + ".out").c_str() , "w+" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Incorrect 49 ms 4296 KB Output isn't correct
12 Incorrect 39 ms 3800 KB Output isn't correct
13 Incorrect 35 ms 3548 KB Output isn't correct
14 Incorrect 52 ms 4056 KB Output isn't correct
15 Incorrect 65 ms 4924 KB Output isn't correct
16 Incorrect 80 ms 5848 KB Output isn't correct
17 Incorrect 57 ms 4568 KB Output isn't correct
18 Incorrect 57 ms 4556 KB Output isn't correct
19 Incorrect 56 ms 4564 KB Output isn't correct
20 Incorrect 57 ms 4708 KB Output isn't correct