oj.uz

답안 #870122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870122 2023-11-07T02:19:07 Z hqminhuwu Zoltan (COCI16_zoltan) C++14
98 / 140
 112 ms 21964 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)
            p[i].nd = (p[i].nd * 2) % mod;
        update1(a[i],p[i]); 
    }
    cout << ans.st << " ";
   // cout << 2 * modpow (2,mod - 2) << "\n";
    if (ans.st == n)
        cout << (ans.nd * modpow(2,mod - 2)) % mod << " ";
    else cout << (ans.nd * modpow(2,n - ans.st - 1)) % 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
98.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 3 ms 11476 KB Output is correct
3 Correct 2 ms 11608 KB Output is correct
4 Incorrect 2 ms 11612 KB Output isn't correct
5 Incorrect 2 ms 11612 KB Output isn't correct
6 Incorrect 2 ms 11612 KB Output isn't 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 Incorrect 66 ms 19240 KB Output isn't correct
12 Incorrect 54 ms 17076 KB Output isn't correct
13 Incorrect 49 ms 16856 KB Output isn't correct
14 Correct 74 ms 17332 KB Output is correct
15 Correct 92 ms 21788 KB Output is correct
16 Correct 112 ms 21964 KB Output is correct
17 Correct 73 ms 21404 KB Output is correct
18 Correct 73 ms 21396 KB Output is correct
19 Correct 74 ms 21412 KB Output is correct
20 Correct 76 ms 21180 KB Output is correct