oj.uz

답안 #577274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577274 2022-06-14T11:40:21 Z NintsiChkhaidze Zoltan (COCI16_zoltan) C++14
140 / 140
 228 ms 19616 KB 
//#include <iostream>
//#include <vector>
//#include <algorithm>
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define int long long

using namespace std;

const int N = 200005,mx = 200005,mod=1000000007;
int a[N];
pair <int,int> inc[N],t[4*N],dc[N];
vector <pair<int,int>> d;

void upd(int h,int l,int r,int idx,int val1,int val2){
    if (l == r){
        if(val1>t[h].f)
            t[h] = {val1,val2};
        else if(val1==t[h].f)
            t[h].s=(t[h].s + val2)%mod;

        return;
    }
    if (idx > (l+r)>>1) upd(right,idx,val1,val2);
    else upd(left,idx,val1,val2);

    if (t[h*2].f == t[h*2 + 1].f) t[h] = {t[h*2].f,(t[h*2+1].s + t[h*2].s)%mod};
    else if(t[h*2].f > t[h*2 + 1].f) t[h] = t[h*2];
    else t[h] = t[h*2 + 1];
}

pair<int,int> get(int h,int l,int r,int L,int R){
    if (r < L || R < l) return {0,0};
    if (L <= l && r <= R) return t[h];
    pair <int,int> x = get(left,L,R),y = get(right,L,R);
    if (x.f == y.f) return {x.f,(x.s+y.s)%mod};
    else if(x.f > y.f) return x;
    return y;
}

void build(int h,int l,int r){
    if (l==r){
        t[h] = {0,0};
        return;
    }
    build(left),build(right);
    t[h] = {0,0};
}

int pwr(int a,int b){
    int res=1;
    while(b){
        if (b%2) res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res;
}
signed main() {
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n;
    cin>>n;
    for(int i =1; i<=n;i++){
        cin>>a[i];
        d.pb({a[i],i});
    }
    sort(d.begin(),d.end());
    a[d[0].s] = 1;
    for (int i=1;i<d.size();i++){
        a[d[i].s] = a[d[i - 1].s];
        if (d[i].f > d[i - 1].f) a[d[i].s]++;
    }
    //increasing
    for (int i = n; i >= 1; i--){
        pair <int,int> g = get(1,1,mx,a[i] + 1,mx);
        inc[i] = {g.f + 1,g.s};
        if (g.f > 0){
            upd(1,1,mx,a[i],g.f+1,g.s);
        }else{
            inc[i].s = 1;
            upd(1,1,mx,a[i],1,1);
        }
    }

    build(1,1,mx);
    //decreasing
    for (int i = n; i >= 1; i--){
        pair <int,int> g = get(1,1,mx,1,a[i] - 1);
        dc[i] = {g.f + 1,g.s};
        if (g.f > 0){
            upd(1,1,mx,a[i],g.f+1,g.s);
        }else{
            dc[i].s = 1;
            upd(1,1,mx,a[i],1,1);
        }
    }
    int mxlen = 0,ans = 0;
    for (int i = 1; i <= n; i++){
        int cur = inc[i].f + dc[i].f - 1;
        if (mxlen == cur){
            ans = (ans + (inc[i].s*dc[i].s)%mod)%mod;
        }else if (mxlen < cur){
            mxlen = cur;
            ans = (inc[i].s*dc[i].s)%mod;
        }
    }

    ans = (ans*pwr(2,n - mxlen))%mod;
    cout<<mxlen<<" "<<ans;
}

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:73:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i=1;i<d.size();i++){
      |                  ~^~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Correct 6 ms 8532 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 6 ms 8532 KB Output is correct
6 Correct 5 ms 8532 KB Output is correct
7 Correct 6 ms 8544 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 5 ms 8532 KB Output is correct
10 Correct 5 ms 8532 KB Output is correct
11 Correct 117 ms 17268 KB Output is correct
12 Correct 105 ms 16172 KB Output is correct
13 Correct 98 ms 15692 KB Output is correct
14 Correct 198 ms 16208 KB Output is correct
15 Correct 169 ms 17964 KB Output is correct
16 Correct 228 ms 19496 KB Output is correct
17 Correct 200 ms 19556 KB Output is correct
18 Correct 167 ms 19504 KB Output is correct
19 Correct 157 ms 19556 KB Output is correct
20 Correct 157 ms 19616 KB Output is correct