Submission #870125

#	Time	Username	Problem	Language	Result	Execution time	Memory
870125		hqminhuwu	Zoltan (COCI16_zoltan)	C++14	112 / 140	109 ms	20152 KiB

zoltan

#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 (stderr)

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 / 140