oj.uz

답안 #370959

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
370959 2021-02-25T09:10:40 Z maozkurt Zoltan (COCI16_zoltan) C++17
98 / 140
 605 ms 38044 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);
    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 = 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
98.0 / 140.0

# 결과 실행 시간 메모리 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 0 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 324 ms 30184 KB Output is correct
12 Correct 278 ms 25064 KB Output is correct
13 Correct 249 ms 23660 KB Output is correct
14 Correct 380 ms 25320 KB Output is correct
15 Runtime error 485 ms 32872 KB Memory limit exceeded
16 Runtime error 605 ms 38044 KB Memory limit exceeded
17 Runtime error 424 ms 36200 KB Memory limit exceeded
18 Runtime error 421 ms 36156 KB Memory limit exceeded
19 Runtime error 437 ms 36200 KB Memory limit exceeded
20 Runtime error 422 ms 36200 KB Memory limit exceeded