oj.uz

Submission #635234

# Submission time Handle Problem Language Result Execution time Memory
635234 2022-08-25T17:16:21 Z IWTIM Zoltan (COCI16_zoltan) C++14
98 / 140
 395 ms 27704 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define dec decc
#define int long long
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, mod = 1e9 + 7;
int n,a[N],inc[N],dec[N],cntinc[N],cntdec[N];
pii tree[4*N][2];
pii merge(pii a, pii b){
    pii c = {0,0};
    if (a.f != b.f) c = max(a,b);
    else c = {a.f, b.s + a.s};
    return c;
}
void update(int node, int le, int ri, int idx, int val, int raod, int ty) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        if (tree[node][ty].f > val) return ;
        if (tree[node][ty].f < val) {
            tree[node][ty] = {val, raod};
            return ;
        }
        tree[node][ty].s += raod;
        return ;
    }
    int mid = (le + ri) / 2;
    update(2 * node,le,mid,idx,val,raod,ty);
    update(2 * node + 1, mid + 1, ri, idx,val,raod,ty);
    tree[node][ty] = merge(tree[2 * node][ty], tree[2 * node + 1][ty]);
}
pii getans(int node, int le, int ri, int start, int end,int ty) {
    if (le > end || ri < start) return {0,0};
    if (le >= start && ri <= end) {
        return tree[node][ty];
    }
    int mid = (le + ri) / 2;
    return merge(getans(2 * node,le,mid,start,end,ty), getans(2 * node + 1, mid + 1, ri, start,end,ty));
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    vector < pii > v;
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        v.pb({a[i],i});
    }
    sort(v.begin(), v.end());
    a[v[0].s] = 1;
    for (int i = 1; i < v.size(); i++) {
        if (v[i].f != v[i - 1].f) a[v[i].s] = a[v[i - 1].s] + 1; 
        else a[v[i].s] = a[v[i - 1].s];
    }
    
    int mx = 0;
    int ans = 0;
    for (int i = n; i >= 1; i--) {
        inc[i] = getans(1,1,n,a[i] + 1,n,0).f + 1;
        dec[i] = getans(1,1,n,1,a[i] - 1,1).f + 1;
        
        cntinc[i] = getans(1,1,n,a[i] + 1, n, 0).s;
        cntdec[i] = getans(1,1,n,1,a[i] - 1, 1).s;
        if (cntinc[i] == 0) cntinc[i] = 1; if (cntdec[i] == 0) cntdec[i] = 1;
        update(1,1,n, a[i], inc[i], cntinc[i],0);
        update(1,1,n, a[i], dec[i], cntdec[i],1);
        //cout<<a[i]<<" "<<inc[i]<<"->"<<cntinc[i]<<"   "<<dec[i]<<"-> "<<cntdec[i]<<"\n";
        mx = max(mx, inc[i] + dec[i] - 1);
    }
    for (int i = n; i >= 1; i--) {
        if (inc[i] + dec[i] - 1 == mx) {
            ans += (cntinc[i] * cntdec[i]) % mod;
            ans %= mod;
        }
    }
    int x = 1;
    for (int i = 1; i <= n - mx; i++) x *= 2, x %= mod;
    cout<<mx<<" "<<ans * x % mod<<"\n";
}

Compilation message

zoltan.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main() {
      | ^~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:52:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 1; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
zoltan.cpp:65:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   65 |         if (cntinc[i] == 0) cntinc[i] = 1; if (cntdec[i] == 0) cntdec[i] = 1;
      |         ^~
zoltan.cpp:65:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   65 |         if (cntinc[i] == 0) cntinc[i] = 1; if (cntdec[i] == 0) cntdec[i] = 1;
      |                                            ^~

Subtask #1
98.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Incorrect 275 ms 25436 KB Output isn't correct
12 Incorrect 224 ms 24376 KB Output isn't correct
13 Incorrect 218 ms 15664 KB Output isn't correct
14 Incorrect 272 ms 24460 KB Output isn't correct
15 Incorrect 353 ms 26228 KB Output isn't correct
16 Incorrect 395 ms 27704 KB Output isn't correct
17 Correct 349 ms 25156 KB Output is correct
18 Correct 321 ms 25136 KB Output is correct
19 Correct 336 ms 25204 KB Output is correct
20 Correct 344 ms 25152 KB Output is correct