oj.uz

답안 #370960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
370960 2021-02-25T09:12:57 Z maozkurt Zoltan (COCI16_zoltan) C++17
112 / 140
 558 ms 23744 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 = 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
112.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 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 Incorrect 2 ms 492 KB Output isn't correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 304 ms 18920 KB Output is correct
12 Correct 263 ms 16488 KB Output is correct
13 Correct 256 ms 15452 KB Output is correct
14 Incorrect 367 ms 16616 KB Output isn't correct
15 Incorrect 456 ms 20456 KB Output isn't correct
16 Incorrect 558 ms 23744 KB Output isn't correct
17 Correct 404 ms 22376 KB Output is correct
18 Correct 430 ms 22380 KB Output is correct
19 Correct 407 ms 22376 KB Output is correct
20 Correct 431 ms 22436 KB Output is correct