oj.uz

Submission #529615

# Submission time Handle Problem Language Result Execution time Memory
529615 2022-02-23T09:11:44 Z cpp219 Zoltan (COCI16_zoltan) C++17
140 / 140
 89 ms 6992 KB 
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll mod = 1e9 + 7;
const ll lg = 20;

ll n,m,a[N],have,ans,kq;

ll add(ll a,ll b){
    a += b;
    if (a >= mod) a -= mod; return a;
}

vector<ll> v;
void compress(){
    sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin());
    for (ll i = 1;i <= n;i++)
        a[i] = lower_bound(v.begin(),v.end(),a[i]) - v.begin() + 1;
}

struct BinaryTree{
    LL bit[N];
    LL merging(LL x,LL y){
        if (x.fs == y.fs) return {x.fs,add(x.sc,y.sc)};
        return max(x,y);
    }
    void upd(ll p,LL x){
        for (ll i = p;i <= n;i += i & -i) bit[i] = merging(bit[i],x);
    }
    LL Get(ll p){
        LL res = {0,0};
        for (ll i = p;i > 0;i -= i & -i) res = merging(res,bit[i]);
        return res;
    }
};
BinaryTree icr,dcr;


int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>a[i],v.push_back(a[i]);
    compress();
    for (ll i = n;i > 0;i--){
        LL cur = icr.Get(n - a[i]),l,r;
        cur.fs++;
        if (cur.fs == 1) cur.sc = 1;
        icr.upd(n - a[i] + 1,cur); l = cur;
        cur = dcr.Get(a[i] - 1);
        cur.fs++;
        if (cur.fs == 1) cur.sc = 1;
        dcr.upd(a[i],cur); r = cur;
        if (l.fs + r.fs - 1 > ans){
            ans = l.fs + r.fs - 1;
            kq = ((long long)l.sc*r.sc) % mod;
        }
        else if (l.fs + r.fs - 1 == ans)
            kq = (kq + (long long)l.sc*r.sc)%mod;
    }
    for (ll i = 1;i <= n - ans;i++) kq = (kq * 2)%mod;
    cout<<ans<<" "<<kq;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

zoltan.cpp: In function 'int add(int, int)':
zoltan.cpp:17:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   17 |     if (a >= mod) a -= mod; return a;
      |     ^~
zoltan.cpp:17:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   17 |     if (a >= mod) a -= mod; return a;
      |                             ^~~~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 0 ms 324 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 48 ms 5284 KB Output is correct
12 Correct 43 ms 4668 KB Output is correct
13 Correct 38 ms 4464 KB Output is correct
14 Correct 60 ms 4968 KB Output is correct
15 Correct 80 ms 6016 KB Output is correct
16 Correct 89 ms 6992 KB Output is correct
17 Correct 62 ms 5832 KB Output is correct
18 Correct 63 ms 5880 KB Output is correct
19 Correct 64 ms 5840 KB Output is correct
20 Correct 66 ms 5880 KB Output is correct