oj.uz

Submission #70653

# Submission time Handle Problem Language Result Execution time Memory
70653 2018-08-23T08:15:41 Z 강태규(#2184) Fibonacci representations (CEOI18_fib) C++11
55 / 100
 356 ms 14340 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
int a[100000];

int cp[100001];

const int mod = 1e9 + 7;

struct matrix {
    int x[2][2];
    matrix() {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                x[i][j] = (i == j);
            }
        }
    }
    matrix operator*(const matrix &p) const {
        matrix ret;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                ret.x[i][j] = 0;
                for (int k = 0; k < 2; ++k) {
                    ret.x[i][j] += (llong)x[i][k] * p.x[k][j] % mod;
                    ret.x[i][j] %= mod;
                }
            }
        }
        return ret;
    }
};

struct node {
    matrix dp;
    int s, e, a;

    void init(int x, int c = 1) {
        s = e = x; a = c;
    }

    node operator+(const node &p) const {
        if (a == 0) return p;
        if (p.a == 0) return *this;

        node ret;
        ret.a = 1;
        ret.s = s;
        ret.e = p.e;
        int d = p.s - e;
        matrix m;
        m.x[0][0] = 1;
        m.x[0][1] = 1;
        m.x[1][0] = (d - 1) / 2;
        m.x[1][1] = d / 2;
        ret.dp = p.dp * m * dp;
        return ret;
    }
} seg[1 << 18];

void active(int i, int s, int e, int x) {
    if (s == e) {
        seg[i].init(cp[s]);
        return;
    }
    int m = (s + e) / 2;
    if (x <= cp[m]) active(i << 1, s, m, x);
    else active(i << 1 | 1, m + 1, e, x);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}

void solve0() {
    for (int i = 0; i < n; ++i) cp[i + 1] = a[i];
    sort(cp + 1, cp + (n + 1));
    active(1, 0, n, 0);
    for (int i = 0; i < n; ++i) {
        active(1, 0, n, a[i]);
        printf("%d\n", (seg[1].dp.x[0][0] + seg[1].dp.x[1][0]) % mod);
    }
}

const int inf = 1e9;
struct dsnode {
    node x;
    dsnode *l, *r;
} * rt;

void update(dsnode * &i, int s, int e, int x, int a) {
    if (i == 0) i = new dsnode();
    if (s == e) {
        i->x.init(s, a);
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(i->l, s, m, x, a);
    else update(i->r, m + 1, e, x, a);
    i->x.init(0, 0);
    if (i->l) i->x = i->x + i->l->x;
    if (i->r) i->x = i->x + i->r->x;
}

void addSet(set<int> &mp, int x) {
    if (x == 0) x = 1;
    if (x == -1) return;
    if (mp.count(x)) {
        update(rt, 0, inf, x, 0);
        mp.erase(x);
        addSet(mp, x - 2);
        addSet(mp, x + 1);
        return;
    }
    if (mp.count(x + 1)) {
        update(rt, 0, inf, x + 1, 0);
        mp.erase(x + 1);
        addSet(mp, x + 2);
        return;
    }
    if (mp.count(x - 1)) {
        update(rt, 0, inf, x - 1, 0);
        mp.erase(x - 1);
        addSet(mp, x + 1);
        return;
    }
    update(rt, 0, inf, x, 1);
    mp.insert(x);
}

void solve1() {
    rt = new dsnode();
    update(rt, 0, inf, 0, 1);
    set<int> mp;
    for (int i = 0; i < n; ++i) {
        addSet(mp, a[i]);
        printf("%d\n", (rt->x.dp.x[0][0] + rt->x.dp.x[1][0]) % mod);
    }
}

int main() {
    scanf("%d", &n);
    int md = 0;
    {
        set<int> mp;
        for (int i = 0; i < n; ++i) {
            scanf("%d", a + i);
            mp.insert(a[i]);
        }
        if (mp.size() == n) {
            md = 1;
            int pr = -1;
            for (int i : mp) {
                if (i - pr == 1) {
                    md = 0;
                    break;
                }
                pr = i;
            }
        }
    }
    if (md) solve0();
    else solve1();
    return 0;
}

Compilation message

fib.cpp: In function 'int main()':
fib.cpp:165:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (mp.size() == n) {
             ~~~~~~~~~~^~~~
fib.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
fib.cpp:162:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", a + i);
             ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 8 ms 7576 KB Output is correct
4 Correct 7 ms 7636 KB Output is correct
5 Correct 8 ms 7840 KB Output is correct
6 Correct 7 ms 7840 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 8 ms 7576 KB Output is correct
4 Correct 7 ms 7636 KB Output is correct
5 Correct 8 ms 7840 KB Output is correct
6 Correct 7 ms 7840 KB Output is correct
7 Correct 10 ms 7840 KB Output is correct
8 Correct 8 ms 7840 KB Output is correct
9 Correct 7 ms 7840 KB Output is correct
10 Correct 8 ms 7840 KB Output is correct
11 Correct 8 ms 7840 KB Output is correct
12 Correct 9 ms 7840 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7840 KB Output is correct
2 Correct 10 ms 7840 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 8 ms 7576 KB Output is correct
4 Correct 7 ms 7636 KB Output is correct
5 Correct 8 ms 7840 KB Output is correct
6 Correct 7 ms 7840 KB Output is correct
7 Correct 10 ms 7840 KB Output is correct
8 Correct 8 ms 7840 KB Output is correct
9 Correct 7 ms 7840 KB Output is correct
10 Correct 8 ms 7840 KB Output is correct
11 Correct 8 ms 7840 KB Output is correct
12 Correct 9 ms 7840 KB Output is correct
13 Correct 8 ms 7840 KB Output is correct
14 Correct 10 ms 7840 KB Output is correct
15 Correct 8 ms 7840 KB Output is correct
16 Correct 7 ms 7840 KB Output is correct
17 Correct 9 ms 7840 KB Output is correct
18 Correct 7 ms 7840 KB Output is correct
19 Incorrect 7 ms 7840 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7840 KB Output is correct
2 Correct 292 ms 14312 KB Output is correct
3 Correct 356 ms 14340 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 8 ms 7576 KB Output is correct
4 Correct 7 ms 7636 KB Output is correct
5 Correct 8 ms 7840 KB Output is correct
6 Correct 7 ms 7840 KB Output is correct
7 Correct 10 ms 7840 KB Output is correct
8 Correct 8 ms 7840 KB Output is correct
9 Correct 7 ms 7840 KB Output is correct
10 Correct 8 ms 7840 KB Output is correct
11 Correct 8 ms 7840 KB Output is correct
12 Correct 9 ms 7840 KB Output is correct
13 Correct 8 ms 7840 KB Output is correct
14 Correct 10 ms 7840 KB Output is correct
15 Correct 8 ms 7840 KB Output is correct
16 Correct 7 ms 7840 KB Output is correct
17 Correct 9 ms 7840 KB Output is correct
18 Correct 7 ms 7840 KB Output is correct
19 Incorrect 7 ms 7840 KB Output isn't correct
20 Halted 0 ms 0 KB -