Submission #997212

#	Time	Username	Problem	Language	Result	Execution time	Memory
997212		TsotneSV	Zoltan (COCI16_zoltan)	C++17	35 / 140	148 ms	65536 KiB

zoltan

#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces

// #define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define mp make_pair
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define sz(x) ((long long) (x).size())
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<" ";
#define printl(x) cout<<(x)<<endl
#define dbg(x) cerr<<#x<<" "<<x<<endl

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

void fileIO(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

 const ll MOD = 1000000007;
// const ll mod = 998244353;
// ll mod;

const int inf=1e9,MAXN=2e5+1; 
const ll INF=1e18; 
const ld pi = 3.14159265358979323846;

// typedef long long ll;
template<typename Node,typename Update>
struct Segtr {

    int s;
    vector<Node> tree;

    void build(int v,int tl,int tr) {
        if(tl == tr) {
            tree[v] = Node(0);
        }else {
            int tm = (tl + tr)/2;
            build(2*v,tl,tm); build(2*v+1,tm+1,tr);
            tree[v].merge(tree[2*v],tree[2*v+1]);
        }
    }

    void update(int v,int idx,int tl,int tr,Update addend) {
        if(tl == tr) {
            addend.apply(tree[v]);
        }else {
            int tm = (tl + tr)/2;
            if(idx <= tm) update(2*v,idx,tl,tm,addend); 
            else update(2*v+1,idx,tm+1,tr,addend);
            tree[v].merge(tree[2*v],tree[2*v+1]);
         //   dbg(tree[2*v].mx); dbg(tree[2*v+1].mx);
           // dbg(tree[v].cnt);
        }
    }

    Node query(int v,int l,int r,int tl,int tr) {
        if(l > r) return Node(0); // *
        else if(tl == l && tr == r) return tree[v];
        int tm = (tl + tr)/2;
        Node L,R,ans;
        L = query(2*v,l,min(r,tm),tl,tm); R = query(2*v+1,max(l,tm+1),r,tm+1,tr);
        ans.merge(L,R);
        return ans;
    }

    Segtr(int n) {
        s = n;
        tree.resize(4*n);
        build(1,0,n-1);
    }

};

struct Node1 {
    ll mx,cnt; // * shecvla sheidzleba

    void merge(Node1 &a,Node1 &b) {

        if(a.mx == 0) {
            mx = b.mx;
            cnt = b.cnt;
            return;
        }else if(b.mx == 0) {
            mx = a.mx;
            cnt = a.cnt;
            return;
        }

        if(a.mx > b.mx) {
            mx = a.mx;
            cnt = a.cnt;
        }else if(a.mx < b.mx) {
            mx = b.mx;
            cnt = b.cnt;
        }else {
            mx = a.mx;
            cnt = (a.cnt % MOD + b.cnt % MOD) % MOD;
        }
    }

    Node1() : mx(0),cnt(1) {}

    Node1(int a) {
        mx = a; 
        cnt = 1;
    }

};

struct Update1 {
    int val,cnt;

    Update1(int val,int cnt) {
        this->val = val;
        this->cnt = cnt;
    }

    void apply(Node1 &a) {

        if(val < a.mx) return;
        else if(val > a.mx) {
            a.mx = val;
            a.cnt = cnt;
        }else {
            a.cnt = (a.cnt % MOD + cnt % MOD) % MOD;
        }
    }


};

int n;

ll binpow(int a,ll b) {

    ll res = 1;

    while(b) {
        if(b&1) res = res * a % MOD;
        a = a * a % MOD;
        b/=2;
    } return res;

}

void solve(int tc = 0){
    cin>>n; int cnt = 0; vi inc,dec,A(n+1);

    for(int i=1;i<=n;i++) {
        cin>>A[i];

        if(i > 1) {
            if(A[i] == A[1]) cnt++;
            else if(A[i] < A[1]) dec.pb(A[i]);
            else inc.pb(A[i]);
        }
    } vi inc1 = inc,dec1 = dec;

    map<int,int> cmp1,cmp2;

    sort(all(inc1)); sort(all(dec1));

    for(int i=0;i<sz(inc1);i++) cmp1[inc1[i]] = i;
    for(int i=0;i<sz(dec1);i++) cmp2[dec1[i]] = i;

    for(int &i : inc) i = cmp1[i];
    for(int &i : dec) i = cmp2[i];

    Segtr<Node1,Update1> T1(sz(cmp1) + 5),T2(sz(cmp2) + 5);


    for(int i : inc) {
        Node1 x = T1.query(1,0,i-1,0,sz(cmp1) -1);
        T1.update(1,i,0,sz(cmp1)-1,Update1(x.mx + 1,x.cnt));
    }

    for(int i : dec) {
        Node1 x = T2.query(1,i+1,sz(cmp2)-1,0,sz(cmp2)-1);
        T2.update(1,i,0,sz(cmp2)-1,Update1(x.mx + 1,x.cnt));
    }

    int ans = T1.tree[1].mx + T2.tree[1].mx + 1;

    cout<<ans<<" "<<((T1.tree[1].cnt * T2.tree[1].cnt % MOD) * binpow(2,n - ans) % MOD * (cnt + 1)) % MOD;

}

signed main(){

  
    send help
  
    int tc=1;
    // cin>>tc;
    for(int t = 0; t < tc; t++) solve(t);
}

Compilation message (stderr)

zoltan.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
zoltan.cpp: In function 'void fileIO(std::string)':
zoltan.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 35 / 140