oj.uz

Submission #582694

# Submission time Handle Problem Language Result Execution time Memory
582694 2022-06-24T09:23:34 Z 반딧불(#8370) Fibonacci representations (CEOI18_fib) C++17
30 / 100
 330 ms 38352 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;


struct Node{
    ll a2a, a2b, b2a, b2b;
    Node(){}
    Node(ll a2a, ll a2b, ll b2a, ll b2b): a2a(a2a), a2b(a2b), b2a(b2a), b2b(b2b){}
    Node operator+(const Node &r)const{
        return Node((a2a*r.a2a+a2b*r.b2a)%MOD, (a2a*r.a2b+a2b*r.b2b)%MOD,
                    (b2a*r.a2a+b2b*r.b2a)%MOD, (b2a*r.a2b+b2b*r.b2b)%MOD);
    }
};

struct segTree{
    Node tree[2000002];

    void init(int i, int l, int r){
        if(l==r){
            tree[i] = Node(1, 0, 0, 1);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void update(int i, int l, int r, int x, Node v){
        if(!x) return;
        if(l==r){
            tree[i] = v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    ll query(){
        return (tree[1].a2a+tree[1].a2b)%MOD;
    }
} tree;

int n;
int arr[100002];
map<int, int> mp;

map<int, int> addition[100002];
set<int> over2;
set<int> consequent;
int phase;

vector<int> vec;
int k;

void delPoint(int x){
    addition[phase][x]--;
    mp[x]--;
    if(mp[x] == 1) over2.erase(x);
    if(!mp[x] && mp[x-1]) consequent.erase(x-1);
    if(!mp[x] && mp[x+1]) consequent.erase(x);
}

void addPoint(int x){
    addition[phase][x]++;
    mp[x]++;
    if(mp[x] >= 2) over2.insert(x);
    if(mp[x-1]) consequent.insert(x-1);
    if(mp[x+1]) consequent.insert(x);

    if(over2.empty()) return;
    if(!consequent.empty()){
        int key = *consequent.rbegin();
        delPoint(key);
        delPoint(key+1);
        addPoint(key+2);
    }
    else if(!over2.empty()){
        int key = *over2.rbegin();
        if(key==1) delPoint(1), delPoint(1), addPoint(2);
        else if(key==2) delPoint(2), delPoint(2), addPoint(1), addPoint(3);
        else delPoint(key), delPoint(key), addPoint(key-1), addPoint(key-2);
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        phase = i;
        addPoint(arr[i]);
        for(auto p: addition[i]){
            if(p.second) vec.push_back(p.first);
        }
    }
    vec.push_back(0);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    k = (int)vec.size()-1;

    set<int> st; /// ����� ��ǥ�� ������
    st.insert(0);
    tree.init(1, 1, k);
    for(int i=1; i<=n; i++){
        for(auto p: addition[i]){
            if(!p.second) continue;
            assert(abs(p.second) == 1);
            int pos = lower_bound(vec.begin(), vec.end(), p.first) - vec.begin();
            if(p.second == 1){ /// �� �߰��ϱ�
                auto it = prev(st.lower_bound(pos));
                tree.update(1, 1, n, pos, Node(1, (p.first-vec[*it]-1)/2, 1, (p.first-vec[*it])/2));
                if(next(it) != st.end()){
                    ++it;
                    tree.update(1, 1, n, *it, Node(1, (vec[*it]-p.first-1)/2, 1, (vec[*it]-p.first)/2));
                }
                st.insert(pos);
            }
            else{ /// �� �����ϱ�
                st.erase(pos);
                auto it = prev(st.lower_bound(pos));
                tree.update(1, 1, n, pos, Node(1, 0, 0, 1));
                if(next(it) != st.end()){
                    ++it;
                    tree.update(1, 1, n, *it, Node(1, (vec[*it]-vec[*prev(it)]-1)/2, 1, (vec[*it]-vec[*prev(it)])/2));
                }
            }
        }
        printf("%lld\n", tree.query());
    }
}

Compilation message

fib.cpp: In function 'int main()':
fib.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
fib.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 330 ms 38352 KB Output is correct
3 Correct 312 ms 37560 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -