oj.uz

Submission #446334

# Submission time Handle Problem Language Result Execution time Memory
446334 2021-07-21T14:56:16 Z LptN21 Zoltan (COCI16_zoltan) C++14
140 / 140
 444 ms 17104 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
//#define oo 2e18
#define eps 1e-9
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
const int N = 4e5+7, M=1e6;
const int MOD = 1e9+7;
const int oo=1e9+1;

int n, m, k, t;

struct Node{
    ii v;
    Node() {v=ii(0, 0);}
    Node(int f, int s) {v=ii(f, s);}
} st[N<<2];

ii add(ii a, ii b) {
    if(a.FF>b.FF) return a;
    else if(a.FF<b.FF) return b;
    return ii(a.FF, (a.SS+b.SS)%MOD);
}
void update(int idx, int l0, int r0, int p, ii v, int t) {
    if(l0>p||r0<p) return;
    if(l0==r0&&l0==p) {
        if (t&1) st[idx].v=add(st[idx].v, v);
        else st[idx].v=v; return;
    }
    int mid=(l0+r0)/2;
    update(idx*2, l0, mid, p, v, t), update(idx*2+1, mid+1, r0, p, v, t);
    st[idx].v=add(st[idx*2].v, st[idx*2+1].v);
}
ii get(int idx, int l0, int r0, int l, int r) {
    if(l0>r||r0<l) return ii(0, 0);
    if(l<=l0&&r0<=r) return st[idx].v;
    int mid=(l0+r0)/2;
    return add(get(idx*2, l0, mid, l, r), get(idx*2+1, mid+1, r0, l, r));
}
void upd(int p, ii v, int t) {update(1, 1, n, p, v, t);}
ii qry(int r) {if(!r) return ii(0, 1);return max(ii(0, 1), get(1, 1, n, 1, r));}

vector<int> b;
int a[N];

int mul(int a, int b) {return (1LL*a*b)%MOD;}
int pw(int a, int b) {
    if(!b) return 1;
    int res=pw(a, b/2); res=mul(res, res);
    if(b&1) res=mul(res, a); return res;
}

signed main() {
    //freopen("sapso.inp", "r", stdin);
    //freopen("sapso.out", "w", stdout);
    //fastIO;
    scanf("%d", &n); ii tmp;
    for(int i=n+1;i<=2*n;a[2*n-i+1]=a[i], b.pb(a[i++])) scanf("%d", &a[i]);
    sort(all(b)), b.resize(unique(all(b))-b.begin());
    for(int i=1;i<=2*n;i++) {
        a[i]=lb(all(b), a[i])-b.begin()+1;
        tmp=qry(a[i]-1);
        upd(a[i], ii(tmp.FF+1, tmp.SS), 1);
    }
    tmp=qry(sz(b));
    if(tmp.FF==n) printf("%d 1", n);
    else printf("%d %d", tmp.FF, mul(tmp.SS, pw(2, n-tmp.FF-1)));
    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special cases (n=1?)
    - do smth instead of do nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message

zoltan.cpp: In function 'void update(int, int, int, int, ii, int)':
zoltan.cpp:39:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   39 |         else st[idx].v=v; return;
      |         ^~~~
zoltan.cpp:39:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   39 |         else st[idx].v=v; return;
      |                           ^~~~~~
zoltan.cpp: In function 'int pw(int, int)':
zoltan.cpp:61:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   61 |     if(b&1) res=mul(res, a); return res;
      |     ^~
zoltan.cpp:61:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   61 |     if(b&1) res=mul(res, a); return res;
      |                              ^~~~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d", &n); ii tmp;
      |     ~~~~~^~~~~~~~~~
zoltan.cpp:69:62: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     for(int i=n+1;i<=2*n;a[2*n-i+1]=a[i], b.pb(a[i++])) scanf("%d", &a[i]);
      |                                                         ~~~~~^~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12748 KB Output is correct
2 Correct 8 ms 12748 KB Output is correct
3 Correct 8 ms 12780 KB Output is correct
4 Correct 8 ms 12740 KB Output is correct
5 Correct 9 ms 12748 KB Output is correct
6 Correct 8 ms 12716 KB Output is correct
7 Correct 9 ms 12768 KB Output is correct
8 Correct 9 ms 12748 KB Output is correct
9 Correct 9 ms 12836 KB Output is correct
10 Correct 9 ms 12840 KB Output is correct
11 Correct 237 ms 16060 KB Output is correct
12 Correct 201 ms 15936 KB Output is correct
13 Correct 185 ms 15420 KB Output is correct
14 Correct 245 ms 16284 KB Output is correct
15 Correct 327 ms 16580 KB Output is correct
16 Correct 444 ms 17104 KB Output is correct
17 Correct 305 ms 16440 KB Output is correct
18 Correct 287 ms 16440 KB Output is correct
19 Correct 288 ms 16440 KB Output is correct
20 Correct 296 ms 16524 KB Output is correct