Submission #943473

#	Time	Username	Problem	Language	Result	Execution time	Memory
943473		idiotcomputer	Zoltan (COCI16_zoltan)	C++11	70 / 140	317 ms	16888 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 (l > r){
        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] = {0,0};
    for (int i =0; i < 4*mxN+1; i++) segtree[i] = {0,0};
    for (int i = n - 1; i >= 0; i--){
        decr[i] = query(0,vals[i]-1,1);
        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};
   /* 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;
    pii c,c2;
    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;  
        c = max(c,c2);
        /*if (c2.f == c.f){
            c.s += c2.s;
        }*/
        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;
    }
    cout << curr << " " << res << "\n";
    
    
    
    
    return 0;
}

• Subtask 1: 70 / 140