oj.uz

Submission #870125

# Submission time Handle Problem Language Result Execution time Memory
870125 2023-11-07T02:21:17 Z hqminhuwu Zoltan (COCI16_zoltan) C++14
112 / 140
 109 ms 20152 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);
        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;
   //         cout << i << " " << ans.st << " " << ans.nd << "\n";
      //  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
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11608 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11608 KB Output is correct
5 Incorrect 2 ms 11612 KB Output isn't correct
6 Correct 2 ms 11612 KB Output is correct
7 Correct 3 ms 11612 KB Output is correct
8 Correct 2 ms 11688 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11612 KB Output is correct
11 Incorrect 62 ms 18008 KB Output isn't correct
12 Incorrect 54 ms 16060 KB Output isn't correct
13 Incorrect 51 ms 15832 KB Output isn't correct
14 Correct 73 ms 16052 KB Output is correct
15 Correct 94 ms 20152 KB Output is correct
16 Correct 109 ms 20152 KB Output is correct
17 Correct 73 ms 20140 KB Output is correct
18 Correct 74 ms 19980 KB Output is correct
19 Correct 82 ms 19996 KB Output is correct
20 Correct 75 ms 20052 KB Output is correct