Submission #943791

#	Time	Username	Problem	Language	Result	Execution time	Memory
943791		idiotcomputer	Zoltan (COCI16_zoltan)	C++11	105 / 140	299 ms	31312 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll,ll>
#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) % mod};
    } 
    return max(a,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){
        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 = comb(c,{0,1});
        c.f += 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 = comb(c,{0,1});
        c.f+=1;
      //  cout << c.f << "," << c.s << " ";
        upd(vals[i],c,0);
    }
  // cout << '\n';
 //   
    
    pii res = {1,n};
    for (int i = 0; i < n; i++){
        c = query(0,vals[i]-1,1);
        c = comb(c,{0,1});
        c2 = query(vals[i],vals[i],0);
        c2 = comb(c2,{0,1});
       // cout << c.f + c2.f << " ," << c.s*c2.s << "\n";
        res = comb(res,{c.f+c2.f,(c.s*c2.s)%mod});
    }
  //  cout << res.s << "\n";
    for (int i = 0; i < n-res.f; i++){
        res.s = (res.s*2) % mod;
    }
  //  cout << res.s << '\n';
    res.s = (res.s * 500000004) % mod;
    cout << res.f << " " << res.s << "\n";
    
    
    
    
    return 0;
}

• Subtask 1: 105 / 140