oj.uz

Submission #370961

# Submission time Handle Problem Language Result Execution time Memory
370961 2021-02-25T09:13:45 Z maozkurt Zoltan (COCI16_zoltan) C++17
140 / 140
 555 ms 23784 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>

#define endl '\n'
#define sp ' '

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn = 2e5+5;
const int mod = 1e9+7;

ll binpow(ll n, ll r){
    ll ret = 1;
    while(r){
        if(r&1)
            ret = ret * n % mod;
        n = n * n % mod;
        r >>= 1;
    }
    return ret;
}   

struct node{
    int len;
    int tane;
};

struct segtree{
    vector<node> t;
    int n;
    segtree (int size){
        n = size;
        t = vector<node>(4 * size);
    }
    node query(int l, int r){
        if(l>r)
            return {0,0};
        return _q(l,r,1,n,1);
    }
    void setit(ll pos, ll tane, ll len){
        _i(pos,tane,len,1,n,1);
    }
    private:
    node _q(int l, int r, int tl, int tr, int v){
        if(tl>tr || tl>r || tr<l)
            return {0,0};
        if(tl>=l && tr <= r)
            return t[v];
        int tm = (tl+tr)/2;
        node sol = _q(l,r,tl,tm,2*v);
        node sag = _q(l,r,tm+1,tr,2*v+1);
        if(sol.len == sag.len){
            return {sol.len,(sol.tane + sag.tane) % mod};
        }
        else if(sol.len>sag.len)
            return sol;
        else
            return sag;
    }
    void _i(ll pos, ll tane, ll len, int tl, int tr, int v){
        if(tl > tr || tl > pos || tr < pos)
            return;
        if(tl == tr){
            assert(tl == pos);
            //assert(t[v].len == 0 && t[v].tane == 0);
            if(t[v].len < len){
                t[v].len = len;
                t[v].tane = tane;
            }
            else if(t[v].len == len){
                t[v].tane = (t[v].tane + tane) % mod;//+=
            }
            return;
        }

        int tm = (tl+tr)/2;
        _i(pos,tane,len,tl,tm,2*v);
        _i(pos,tane,len,tm+1,tr,2*v+1);

        if(t[2*v].len > t[2*v+1].len){
            t[v] = t[2*v];
        }
        else if(t[2*v].len < t[2*v+1].len){
            t[v] = t[2*v+1];
        }
        else{
            t[v] = {t[2*v].len, (t[2*v].tane + t[2*v+1].tane) % mod};
        }
        return;
    }
};

int main(){

    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);

    int n;cin>>n;

    vector<int> arr(n);
    vector<int> sorted;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        sorted.pb(arr[i]);
    }
    sort(sorted.begin(),sorted.end());
    sorted.resize(unique(sorted.begin(),sorted.end()) - sorted.begin());
    map<int,int> mm;
    for(int i=1;i<=(int)sorted.size();i++){
        mm[sorted[i-1]] = i;
    }

    for(int i=0;i<(int)arr.size();i++){
        arr[i] = mm[arr[i]];
    }
    
    segtree inctree(n+1), dectree(n+1);
    
    ll ans = 0;
    ll anslen = 0;

    for(int i=n-1;i>=0;i--){
        node sol = dectree.query(arr[i]+1,n);
        node sag = inctree.query(1,arr[i]-1);
        ll curlen = sol.len + sag.len + 1;
        
        ll curtane;
        if(sol.tane == 0 && sag.tane == 0)
            curtane = 1;
        else if(sol.tane == 0)
            curtane = sag.tane;
        else if(sag.tane == 0)
            curtane = sol.tane;
        else
            curtane = (ll)sol.tane * sag.tane % mod;
        
        curtane = curtane * binpow(2,n-curlen) % mod;      

        if(curlen>anslen){
            ans = curtane;
            anslen = curlen;
        }
        else if(curlen == anslen){
            ans = (ans + curtane) % mod;
        }
        //cerr << arr[i] << sp << sol.len << sp << sol.tane << endl;
        //cerr << arr[i] << sp << sag.len << sp << sag.tane << endl;
        dectree.setit(arr[i],max(1,sol.tane),sol.len+1);
        inctree.setit(arr[i],max(1,sag.tane),sag.len+1);
    }

    cout << anslen << sp << ans << endl;

}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 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 0 ms 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 325 ms 18920 KB Output is correct
12 Correct 255 ms 16488 KB Output is correct
13 Correct 239 ms 15616 KB Output is correct
14 Correct 384 ms 16588 KB Output is correct
15 Correct 474 ms 20524 KB Output is correct
16 Correct 555 ms 23784 KB Output is correct
17 Correct 428 ms 22376 KB Output is correct
18 Correct 411 ms 22344 KB Output is correct
19 Correct 405 ms 22248 KB Output is correct
20 Correct 415 ms 22376 KB Output is correct