oj.uz

Submission #870128

# Submission time Handle Problem Language Result Execution time Memory
870128 2023-11-07T02:24:43 Z hqminhuwu Zoltan (COCI16_zoltan) C++14
140 / 140
 107 ms 20156 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,ll>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int i,n,a[N];
pii bit[N];
pll ans;

ll modpow (ll u, ll v){
    if (v == 0)
        return 1;
    ll tmp = modpow(u,v / 2);
    tmp = (tmp * tmp) % mod;
    if (v & 1)
        return (tmp * u) % mod;
    return tmp;
}
void update1 (int u, pll len){
    for (; u <= n; u += u & -u)
    if (bit[u].st < len.st)
        bit[u] = len;
    else if (bit[u].st == len.st)
        (bit[u].nd += len.nd) %= mod;
}

pll get1 (int u){
    pll res = {0,1};
    for (; u > 0; u -= u & -u)
    if (res.st < bit[u].st)
        res = bit[u];
    else if (res.st == bit[u].st)
        (res.nd += bit[u].nd) %= mod;
    return res;
}

void update2 (int u, pll len){
    for (; u > 0; u -= u & -u)
    if (bit[u].st < len.st)
        bit[u] = len;
    else if (bit[u].st == len.st)
        (bit[u].nd += len.nd) %= mod;
}

pll get2 (int u){
    pll res = {0,1};
    for (; u <= n; u += u & -u)
    if (res.st < bit[u].st)
        res = bit[u];
    else if (res.st == bit[u].st)
        (res.nd += bit[u].nd) %= mod;
    return res;
}
void compr(){
    vector <int> w;
    forr (i,1,n)
        w.pb(a[i]);
    sort(all(w));
    w.erase(unique(all(w)),w.end());
    forr (i,1,n)
        a[i] = lower_bound(all(w),a[i]) - w.begin() + 1;
}

pll p[N],s[N];
vector <int> v;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    forr (i,1,n)
        cin >> a[i];
    compr();
    ford (i,n,1){
        pii u = get1(a[i] - 1);
        p[i] = {u.st + 1,u.nd};
        update1(a[i],p[i]);
    }
    memset(bit,0,sizeof bit);
    ford (i,n,1){
        pii u = get2(a[i] + 1);
        s[i] = {u.st + 1,u.nd};
        update2(a[i],s[i]);
    }
    memset(bit,0,sizeof bit);
    forr (i,1,n){
       // cout << a[i] << " " << p[i].st << " " << p[i].nd << " " << s[i].st << " " << s[i].nd << "\n";
        pll k = get1(a[i] - 1);
        if (k.st != 1){
        pll w = {k.st + s[i].st,(k.nd *s[i].nd) % mod};
        if (w.st > ans.st)
            ans = w;
        else if (ans.st == w.st)
            ans.nd = (ans.nd + w.nd) % mod;
        }
      //  if (i == 1)
        update1(a[i],p[i]); 
    }
    cout << ans.st << " ";
   // cout << 2 * modpow (2,mod - 2) << "\n";
    cout << (ans.nd * modpow(2,n - ans.st)) % mod;
    return 0;
}
/*



*/

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:95:28: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   95 |     memset(bit,0,sizeof bit);
      |                            ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from zoltan.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
zoltan.cpp:101:28: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
  101 |     memset(bit,0,sizeof bit);
      |                            ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from zoltan.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11608 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11620 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 2 ms 11612 KB Output is correct
7 Correct 2 ms 11612 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11612 KB Output is correct
11 Correct 60 ms 18008 KB Output is correct
12 Correct 53 ms 15932 KB Output is correct
13 Correct 54 ms 16096 KB Output is correct
14 Correct 72 ms 16036 KB Output is correct
15 Correct 93 ms 20000 KB Output is correct
16 Correct 107 ms 20032 KB Output is correct
17 Correct 76 ms 20064 KB Output is correct
18 Correct 73 ms 20156 KB Output is correct
19 Correct 73 ms 20008 KB Output is correct
20 Correct 75 ms 20056 KB Output is correct