Submission #943536

#	Time	Username	Problem	Language	Result	Execution time	Memory
943536		idiotcomputer	Zoltan (COCI16_zoltan)	C++11	77 / 140	225 ms	18004 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;
int n;

pii decr[mxN];

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 < n; i++) decr[i] = {1,1};
    for (int i =0; i < 4*mxN+1; i++) segtree[i] = {0,0};
   // upd(0,{0,1},1);
    pii c,c2;
    for (int i = n - 1; i >= 0; i--){
      //  cout << vals[i]-1 << " ";
        c = query(0,vals[i]-1,1);
        c.f += 1;
        decr[i] = max(decr[i],c);
       // decr[i].f += 1;
      /*  if (decr[i].f == 1){
            decr[i].s += 1;
        }*/
        upd(vals[i],decr[i],1);
    }
    
    for (int i =0; i < 4*mxN+1; i++) segtree2[i] = {0,0};
  //  upd(0,{0,1},0);
 /*   for (int i =0; i < n; i++) cout << decr[i].f << ',' << decr[i].s << " ";
    cout << '\n';
    for (int i =0; i < n; i++) cout << vals[i] << " ";
    cout << '\n';*/
    curr = -1;
    cnt = 0;
    for (int i =0; i < n; i++){
        c = query(0,vals[i]-1,0);
        c.f += 1;
        c2 = query(0,vals[i]-1,1);
        c2.f += 1;
     //   if (c2.f == 1) c2.s += 1;  
        /*if (c.f < c2.f){
            swap(c,c2);
        }
        if (c2.f == c.f){
            c.s += c2.s;
        }*/
        c = comb(c,c2);
        c = max(c,{1,1});
        if (c.f > curr){
            curr = c.f;
            cnt = c.s;
        } else if (c.f == curr){
            cnt += c.s;
        }
        
        //cout << c.f << "," << c.s << " ";
        upd(vals[i],c,0);
    }
   // cout << '\n';
    ll mod = 1e9+7;
    ll res = cnt;
    for (int i = 0; i < n-curr; i++){
        res = (res*2) % mod;
    }
    res = (res * 500000004) % mod;
    cout << curr << " " << res << "\n";
    
    
    
    
    return 0;
}

• Subtask 1: 77 / 140