oj.uz

Submission #519212

# Submission time Handle Problem Language Result Execution time Memory
519212 2022-01-26T02:46:29 Z XII Zoltan (COCI16_zoltan) C++17
21 / 140
 260 ms 10124 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "COCI16_zoltan"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 2e5 + 1;
const int MOD = 1e9 + 7;
int a[N], n;
vector<int> X;
using pi = pair<int, int>;
pi comb(const pi &a, const pi &b){
    return a.fi == b.fi ? mp(a.fi, (a.se + b.se) % MOD)
                        : (a.fi > b.fi) ? a : b;
}

int lz[N * 4];
pi ST[N * 4];

int mul(const int &a, const int &b){
    return (1LL * a * b) % MOD;
}

void down(int id){
    ST[id * 2].se = mul(ST[id * 2].se, lz[id]);
    ST[id * 2 + 1].se = mul(ST[id * 2 + 1].se, lz[id]);
    lz[id * 2] = mul(lz[id * 2], lz[id]);
    lz[id * 2 + 1] = mul(lz[id * 2 + 1], lz[id]);
    lz[id] = 1;
}

void update(const int &i, const pi &v, int id = 1, int be = 1, int en = X.size()){
    if(be == en){
        ST[id] = comb(ST[id], v);
        return;
    }
    int mi = (be + en) / 2;
    if(lz[id] > 1) down(id);
    if(i <= mi) update(i, v, id * 2, be, mi);
    else update(i, v, id *  2 + 1, mi + 1, en);
    ST[id] = comb(ST[id * 2], ST[id * 2 + 1]);
}

void updateChoice(){
    ST[1].se = (ST[1].se * 2) % MOD;
    lz[1] = (lz[1] * 2) % MOD;
}

pi query(const int &l, const int &r, int id = 1, int be = 1, int en = X.size()){
    if(r < be || en < l) return {0, 0};
    if(l <= be && en <= r) return ST[id];
    int mi = (be + en) / 2;
    if(lz[id] > 1) down(id);
    return comb(query(l, r, id * 2, be, mi), query(l, r, id * 2 + 1, mi + 1, en));
}

int p2[N];
void init(){
    p2[0] = 1;
    FORU(i, 1, n) p2[i] = (p2[i - 1] * 2) % MOD;
}

int main(){
    IOS;
    Fi();
    cin >> n;
    init();
    FORU(i, 1, n){
        cin >> a[i];
        X.eb(a[i]);
    }
    memset(lz, 1, sizeof(lz));
    sort(ALL(X));
    X.resize(unique(ALL(X)) - X.begin());
    pi ans = {0, 0};

    FORU(i, 1, n){
        a[i] = lower_bound(ALL(X), a[i]) - X.begin() + 1;
        pi lef = query(a[i] + 1, X.size()); lef.fi += 1;
        pi rig = query(1, a[i] - 1); rig.fi += 1;
        updateChoice();
        pi tmp = comb({1, p2[i - 1]}, comb(lef, rig));
        update(a[i], tmp);
        tmp.se = mul(tmp.se, p2[n - i]);
        ans = comb(ans, tmp);
    }
    cout << ans.fi << " " << ans.se;
    return 0;
}

Compilation message

zoltan.cpp: In function 'void Fi()':
zoltan.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3404 KB Output isn't correct
2 Incorrect 2 ms 3404 KB Output isn't correct
3 Incorrect 2 ms 3404 KB Output isn't correct
4 Correct 1 ms 3404 KB Output is correct
5 Correct 1 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Incorrect 2 ms 3404 KB Output isn't correct
8 Incorrect 3 ms 3404 KB Output isn't correct
9 Incorrect 2 ms 3404 KB Output isn't correct
10 Incorrect 2 ms 3496 KB Output isn't correct
11 Incorrect 155 ms 9496 KB Output isn't correct
12 Incorrect 151 ms 9220 KB Output isn't correct
13 Incorrect 125 ms 7056 KB Output isn't correct
14 Incorrect 160 ms 9248 KB Output isn't correct
15 Incorrect 229 ms 9664 KB Output isn't correct
16 Incorrect 260 ms 10012 KB Output isn't correct
17 Incorrect 205 ms 10028 KB Output isn't correct
18 Incorrect 210 ms 10008 KB Output isn't correct
19 Incorrect 210 ms 10124 KB Output isn't correct
20 Incorrect 205 ms 10016 KB Output isn't correct