oj.uz

Submission #577269

# Submission time Handle Problem Language Result Execution time Memory
577269 2022-06-14T11:31:34 Z NintsiChkhaidze Zoltan (COCI16_zoltan) C++14
112 / 140
 218 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){
        t[h].f=val1;
        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;
        }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
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 8 ms 8532 KB Output is correct
3 Correct 7 ms 8524 KB Output is correct
4 Correct 7 ms 8488 KB Output is correct
5 Correct 6 ms 8532 KB Output is correct
6 Correct 5 ms 8532 KB Output is correct
7 Correct 5 ms 8532 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 5 ms 8512 KB Output is correct
10 Correct 6 ms 8532 KB Output is correct
11 Correct 123 ms 17280 KB Output is correct
12 Correct 128 ms 16148 KB Output is correct
13 Correct 139 ms 15676 KB Output is correct
14 Correct 170 ms 16224 KB Output is correct
15 Correct 176 ms 18064 KB Output is correct
16 Correct 199 ms 19472 KB Output is correct
17 Incorrect 157 ms 19572 KB Output isn't correct
18 Incorrect 152 ms 19544 KB Output isn't correct
19 Incorrect 179 ms 19616 KB Output isn't correct
20 Incorrect 218 ms 19540 KB Output isn't correct