oj.uz

Submission #577271

# Submission time Handle Problem Language Result Execution time Memory
577271 2022-06-14T11:33:07 Z NintsiChkhaidze Zoltan (COCI16_zoltan) C++14
112 / 140
 232 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=(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: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 5 ms 8532 KB Output is correct
3 Correct 5 ms 8496 KB Output is correct
4 Correct 5 ms 8532 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 5 ms 8532 KB Output is correct
7 Correct 6 ms 8532 KB Output is correct
8 Correct 6 ms 8592 KB Output is correct
9 Correct 5 ms 8532 KB Output is correct
10 Correct 6 ms 8532 KB Output is correct
11 Correct 131 ms 17304 KB Output is correct
12 Correct 117 ms 16148 KB Output is correct
13 Correct 169 ms 15744 KB Output is correct
14 Correct 140 ms 16156 KB Output is correct
15 Correct 232 ms 17960 KB Output is correct
16 Correct 214 ms 19440 KB Output is correct
17 Incorrect 177 ms 19576 KB Output isn't correct
18 Incorrect 156 ms 19532 KB Output isn't correct
19 Incorrect 152 ms 19708 KB Output isn't correct
20 Incorrect 174 ms 19512 KB Output isn't correct