oj.uz

Submission #1102120

# Submission time Handle Problem Language Result Execution time Memory
1102120 2024-10-17T13:46:03 Z KawakiMeido Zoltan (COCI16_zoltan) C++17
98 / 140
 222 ms 20020 KB 
/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 2e5+10;
const int INF = 1e9+7;
const int MD = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

/*Global Variables*/
int n;
vector<int> cmp;
vector<pair<pii,pii>> query;

//SEGG
pii STLDS[N*4], STLIS[N*4];
pii ansLDS[N],ansLIS[N];
ll prelg2[N];

pii Comb(pii x, pii y){
    if (x.fi!=y.fi){
        return max(x,y);
    }
    else return make_pair(x.fi,(x.se+y.se)%MD);
}

void Update(int idx, int l, int r, int x, pii val, pii ST[N*4]){
    if (x<l || r<x) return;
    if (l==r){
        ST[idx] = Comb(val,ST[idx]);
        return;
    }
    int mid = (l+r)/2;
    Update(idx*2,l,mid,x,val,ST); Update(idx*2+1,mid+1,r,x,val,ST);
    ST[idx] = Comb(ST[idx*2],ST[idx*2+1]);
}

pii Get(int idx, int l, int r, int x, int y, pii ST[N*4]){
    if (y<l || r<x) return make_pair(0,0);
    if (x<=l && r<=y) return ST[idx];
    int mid = (l+r)/2;
    return Comb(Get(idx*2,l,mid,x,y,ST),Get(idx*2+1,mid+1,r,x,y,ST));
}

/*Solution*/
void solve(){
    cin >> n;
    prelg2[0] = 1;
    for (int i=1; i<=n+10; i++){
        prelg2[i] = (prelg2[i-1]*2)%MD;
    }
    for (int i=1; i<=n; i++){
        int x; cin >> x;
        cmp.push_back(x);
        query.push_back({{i,0},{x,i}});
    }
    sort(all(cmp));
    cmp.resize(unique(all(cmp))-cmp.begin());
    for (int i=0; i<(int)query.size(); i++){
        query[i].se.fi = lower_bound(all(cmp),query[i].se.fi) - cmp.begin()+1;
    }
    sort(all(query),greater<pair<pii,pii>>());
    int mx = 0;
    int idx = 0;
    for (int i=n; i>0; i--){
        while (idx!=(int)query.size() && query[idx].fi.fi == i){
            int x = query[idx].se.fi;
            int ver = query[idx].fi.se;
            int id = query[idx].se.se;

            pii tmpLIS = Get(1,1,cmp.size(),1,x-1,STLIS);
            pii tmpLDS = Get(1,1,cmp.size(),x+1,cmp.size(),STLDS);

            if (tmpLIS.fi == 0) ++tmpLIS.se;
            if (tmpLDS.fi == 0) ++tmpLDS.se;

            tmpLIS.fi++;
            tmpLDS.fi++;

//            cout << tmpLIS.fi << " " << tmpLIS.se << " " << tmpLDS.fi << " " << tmpLDS.se << endl;

            mx = max(tmpLIS.fi+tmpLDS.fi-1,mx);

            Update(1,1,cmp.size(),x,tmpLIS,STLIS);
            Update(1,1,cmp.size(),x,tmpLDS,STLDS);

            ansLIS[id] = tmpLIS;
            ansLDS[id] = tmpLDS;

            ++idx;
        }
    }

    long long res = 0;
    for (int i=1; i<=n; i++){
        if (ansLIS[i].fi+ansLDS[i].fi-1 == mx){
            res+=(((ll)ansLIS[i].se*ansLDS[i].se)%MD*prelg2[n-mx])%MD;
//            cout << res << endl;
        }
    }
    cout << mx << " " << res << endl;
}

/*Driver Code*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    TestCases(0);

    return 0;
}

Compilation message

zoltan.cpp: In function 'void solve()':
zoltan.cpp:85:17: warning: unused variable 'ver' [-Wunused-variable]
   85 |             int ver = query[idx].fi.se;
      |                 ^~~

Subtask #1
98.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Incorrect 1 ms 592 KB Output isn't correct
8 Incorrect 2 ms 592 KB Output isn't correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 140 ms 17712 KB Output is correct
12 Correct 124 ms 15408 KB Output is correct
13 Correct 105 ms 11068 KB Output is correct
14 Correct 145 ms 15416 KB Output is correct
15 Correct 198 ms 18052 KB Output is correct
16 Correct 222 ms 20020 KB Output is correct
17 Incorrect 208 ms 19564 KB Output isn't correct
18 Incorrect 183 ms 18600 KB Output isn't correct
19 Incorrect 170 ms 18908 KB Output isn't correct
20 Incorrect 172 ms 19248 KB Output isn't correct