Submission #943562

#	Time	Username	Problem	Language	Result	Execution time	Memory
943562		idiotcomputer	Zoltan (COCI16_zoltan)	C++11	49 / 140	264 ms	15440 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first 
#define s second
#define ll long long int

const int mxN = 2*1e5;
const ll mod = 1e9+7;
int n;

pii segtree[4*mxN+1];
pii segtree2[4*mxN+1];

pii comb(pii a, pii b){
    if (a.f == b.f){
        return {a.f,a.s+b.s};
    } 
    if (a.f > b.f){
        return a;
    }
    return b;
}

void upd(int t, pii v, bool w, int l = 0, int r = n-1, int idx = 0){
    if (l > t || r < t){
        return;
    }
    if (l == r){
        if (w) segtree[idx] = comb(v,segtree[idx]);
        else segtree2[idx] = comb(v,segtree2[idx]);
        return;
    }
    int m = (l+r)/2;
    upd(t,v,w,l,m,2*idx+1);
    upd(t,v,w,m+1,r,2*idx+2);
    if (w) segtree[idx] = comb(segtree[2*idx+1],segtree[2*idx+2]);
    else segtree2[idx] = comb(segtree2[2*idx+1],segtree2[2*idx+2]);
    return;
}

pii query(int tl, int tr, bool w, int l = 0, int r = n-1, int idx = 0){
    if (tl > tr){
       // cout << "HEr\n";
        return {0,0};
    }
    if (l > tr || r < tl){
        return {0,0};
    }
    if (l >= tl && r <= tr){
        if (w) return segtree[idx];
        return segtree2[idx];
    }
    int m = (l+r)/2;
    return comb(query(tl,tr,w,l,m,2*idx+1),query(tl,tr,w,m+1,r,2*idx+2));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    
    vector<int> vals(n);
    vector<pii> temp(n);
    for (int i = 0; i < n; i++){
        cin >> vals[i];
        temp[i].f = vals[i];
        temp[i].s =  i;
    }
    sort(temp.begin(),temp.end());
    int curr = -1;
    int cnt = -1;
    for (int i =0; i < n; i++){
        if (temp[i].f != curr){
            curr = temp[i].f;
            cnt++;
        }
        vals[temp[i].s] = cnt;
    }
    
    for (int i =0; i < 4*mxN+1; i++) segtree[i] = {0,0};
    pii c,c2;
    for (int i = n - 1; i >= 0; i--){
        c = query(0,vals[i]-1,1);
        c.f += 1;
        c = max(c,{1,1});
        //cout << c.f << ',' << c.s << " ";
        upd(vals[i],c,1);
    }
  //  cout << '\n';
    for (int i =0; i < 4*mxN+1; i++) segtree2[i] = {0,0};
    for (int i = n-1; i >= 0; i--){
        c = query(vals[i]+1,n-1,0);
        c.f += 1;
        c = max(c,{1,1});
       // cout << c.f << "," << c.s << " ";
        upd(vals[i],c,0);
    }
   // cout << '\n';
    
    
    curr = -1;
    ll res = 0;
    for (int i = 0; i < n; i++){
        c = query(0,vals[i]-1,1);
        c = max(c,{0,1});
        c2 = query(vals[i],vals[i],0);
        c2 = max(c2,{1,1});
      //  cout << c.f + c2.f << " ," << c.s*c2.s << " " << curr << '\n';
        if (c.f+c2.f> curr){
            curr = c.f+c2.f;
            res = (c.s*c2.s)%mod;
        } else if (c.f+c2.f == curr){
            res = (res + c.s*c2.s) % mod;
        }
    }
   // cout << res << '\n';
    for (int i = 0; i < n-curr; i++){
        res = (res*2) % mod;
    }
 //   cout << res << '\n';
    res = (res * 500000004) % mod;
    cout << curr << " " << res << "\n";
    
    
    
    
    return 0;
}

• Subtask 1: 49 / 140