oj.uz

Submission #370958

# Submission time Handle Problem Language Result Execution time Memory
370958 2021-02-25T09:01:59 Z maozkurt Zoltan (COCI16_zoltan) C++17
0 / 140
 1000 ms 65536 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 ll 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{
    ll len;
    ll 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);
    set<int> sorted;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        sorted.insert(arr[i]);
    }

    map<int,int> mm;
    auto it = sorted.begin();
    for(int i=1;i<=(int)sorted.size();i++){
        mm[*it] = i;
        ++it;
    }

    for(int i=0;i<(int)arr.size();i++){
        arr[i] = mm[arr[i]];
    }
    
    segtree inctree(n), dectree(n);
    
    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 = 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(1LL,sol.tane),sol.len+1);
        inctree.setit(arr[i],max(1LL,sag.tane),sag.len+1);
    }

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

}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 364 KB Time limit exceeded
2 Execution timed out 1051 ms 364 KB Time limit exceeded
3 Execution timed out 1083 ms 364 KB Time limit exceeded
4 Execution timed out 1093 ms 364 KB Time limit exceeded
5 Execution timed out 1082 ms 364 KB Time limit exceeded
6 Runtime error 1 ms 492 KB Execution killed with signal 11
7 Execution timed out 1088 ms 640 KB Time limit exceeded
8 Execution timed out 1088 ms 620 KB Time limit exceeded
9 Execution timed out 1086 ms 620 KB Time limit exceeded
10 Execution timed out 1070 ms 620 KB Time limit exceeded
11 Runtime error 199 ms 65536 KB Execution killed with signal 7
12 Runtime error 203 ms 63468 KB Execution killed with signal 7
13 Runtime error 156 ms 60012 KB Execution killed with signal 7
14 Runtime error 225 ms 64236 KB Execution killed with signal 7
15 Runtime error 326 ms 65536 KB Execution killed with signal 7
16 Runtime error 369 ms 65536 KB Execution killed with signal 7
17 Runtime error 247 ms 65536 KB Execution killed with signal 7
18 Runtime error 236 ms 65536 KB Execution killed with signal 7
19 Runtime error 234 ms 65536 KB Execution killed with signal 7
20 Runtime error 228 ms 65536 KB Execution killed with signal 7