oj.uz

Submission #1102115

# Submission time Handle Problem Language Result Execution time Memory
1102115 2024-10-17T13:38:42 Z KawakiMeido Zoltan (COCI16_zoltan) C++17
98 / 140
 220 ms 19248 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];
int 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; 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 504 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Incorrect 2 ms 336 KB Output isn't correct
8 Incorrect 1 ms 592 KB Output isn't correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 1 ms 480 KB Output is correct
11 Correct 148 ms 16920 KB Output is correct
12 Correct 120 ms 15920 KB Output is correct
13 Correct 108 ms 10892 KB Output is correct
14 Correct 139 ms 16432 KB Output is correct
15 Correct 194 ms 17968 KB Output is correct
16 Correct 220 ms 19248 KB Output is correct
17 Incorrect 175 ms 18736 KB Output isn't correct
18 Incorrect 159 ms 18740 KB Output isn't correct
19 Incorrect 167 ms 18736 KB Output isn't correct
20 Incorrect 163 ms 18580 KB Output isn't correct