oj.uz

Submission #943473

# Submission time Handle Problem Language Result Execution time Memory
943473 2024-03-11T14:05:51 Z idiotcomputer Zoltan (COCI16_zoltan) C++11
70 / 140
 317 ms 16888 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12984 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12760 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Incorrect 3 ms 12888 KB Output isn't correct
8 Correct 4 ms 12892 KB Output is correct
9 Incorrect 3 ms 12892 KB Output isn't correct
10 Correct 4 ms 12892 KB Output is correct
11 Incorrect 155 ms 16064 KB Output isn't correct
12 Incorrect 135 ms 15440 KB Output isn't correct
13 Incorrect 124 ms 15320 KB Output isn't correct
14 Incorrect 163 ms 15496 KB Output isn't correct
15 Incorrect 277 ms 16328 KB Output isn't correct
16 Incorrect 285 ms 16856 KB Output isn't correct
17 Correct 213 ms 16644 KB Output is correct
18 Incorrect 317 ms 16888 KB Output isn't correct
19 Correct 207 ms 16708 KB Output is correct
20 Incorrect 214 ms 16708 KB Output isn't correct