Submission #997227

#	Time	Username	Problem	Language	Result	Execution time	Memory
997227		TsotneSV	Zoltan (COCI16_zoltan)	C++17	42 / 140	173 ms	21176 KiB

zoltan

#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/
//#pragma comment(linker, "/stack:200000000")

// #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 = 1e9+7;
// 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]);
        }
    }

    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() {}

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

};

struct Update1 {
    int val; ll cnt;

    Update1(int val,ll 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; vi A,v;

    for(int i=0;i<n;i++) {
        int tmp;
        cin>>tmp;
        A.pb(tmp);
        v.pb(tmp);
    } sort(all(v)); v.resize(unique(all(v)) - v.begin());

    for(int i=0;i<n;i++) {
        A[i] = lower_bound(all(v),A[i]) - v.begin();
    }

    Segtr<Node1,Update1> T1(sz(v)),T2(sz(v));

    int len = 0; ll cnt = 0;


    for(int i=sz(A)-1;i>=0;i--) {

        Node1 x1 = T1.query(1,0,A[i]-1,0,sz(v)-1);
        Node1 x2 = T2.query(1,A[i]+1,sz(v)-1,0,sz(v)-1);

        int tLen = x1.mx + x2.mx + 1; ll tCnt = x1.cnt * x2.cnt % MOD;

        if(tLen > len) {
            len = tLen;
            cnt = tCnt;
        }else if(tLen == len) {
            cnt = (cnt + tCnt) % MOD;
        }

        // ......

        T1.update(1,A[i],0,sz(v)-1,Update1(x1.mx + 1,x1.cnt));
        T2.update(1,A[i],0,sz(v)-1,Update1(x2.mx + 1,x2.cnt));

    } cout<<len<<" "<<cnt * binpow(2,n - len) % MOD<<endl;

}

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:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 42 / 140