oj.uz

Submission #577267

# Submission time Handle Problem Language Result Execution time Memory
577267 2022-06-14T11:30:16 Z NintsiChkhaidze Zoltan (COCI16_zoltan) C++14
70 / 140
 224 ms 19708 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){
        t[h].f=val1;
        t[h].s+=val2;
        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};
    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};
    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;
        }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:70: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]
   70 |     for (int i=1;i<d.size();i++){
      |                  ~^~~~~~~~~

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 5 ms 8532 KB Output is correct
5 Correct 5 ms 8452 KB Output is correct
6 Correct 5 ms 8448 KB Output is correct
7 Correct 6 ms 8540 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 6 ms 8532 KB Output is correct
10 Correct 5 ms 8532 KB Output is correct
11 Incorrect 131 ms 17268 KB Output isn't correct
12 Incorrect 102 ms 16176 KB Output isn't correct
13 Incorrect 98 ms 15644 KB Output isn't correct
14 Incorrect 193 ms 16184 KB Output isn't correct
15 Incorrect 209 ms 18044 KB Output isn't correct
16 Incorrect 224 ms 19504 KB Output isn't correct
17 Incorrect 148 ms 19616 KB Output isn't correct
18 Incorrect 152 ms 19568 KB Output isn't correct
19 Incorrect 162 ms 19708 KB Output isn't correct
20 Incorrect 147 ms 19588 KB Output isn't correct